题目 题目链接 image-20220214215346985题目详解 这题本应是简单题，就是简单的异或规律，但是题目要求使用 O(logn) 时间复杂度， O(1) 空间复杂度，而如果直接异或，只会是 O(n) 的时间复杂度。 那么该如何去做呢？ 这题有二段性，什么叫二段性呢，就是能有一个分界点把特性一分为二。比如此题由于数据是有序的，所以数量为两个的元素会挨在一起，而且在 单身狗 左边连续的元素下标会有以下规律：两个相邻的相同元素中，第一个元素下标会是偶数，第二个是奇数。右边的连续元素下标会有以下规律：两个相邻的相同元素中，第一个元素下标是奇数，第二个是偶数。 根据以上二段性可很快构建出二分版本的代码！解题代码 未简化二分版本class Solution { public: int singleNonDuplicate(vector<int>& nums) { int l=0,r=nums.size()-1; int maxr = r; int mid; while(l<r){ mid = (l+r)/2; if(mid<maxr&&nums[mid+1]==nums[mid]){ if(mid%2==0){ l = mid+2; }else{ r = mid; } }else if(mid>0&&nums[mid-1]==nums[mid]){ if((mid-1)%2==0){ l = mid+1; }else{ r = mid; } }else{ return nums[mid]; } } return nums[l]; } }; 简化的二分版本class Solution { public: int singleNonDuplicate(vector<int>& nums) { int low = 0, high = nums.size() - 1; while (low < high) { int mid = (high - low) / 2 + low; if (nums[mid] == nums[mid ^ 1]) { low = mid + 1; } else { high = mid; } } return nums[low]; } };