题目
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8] 输出: 2
示例 2:
输入: nums = [3,3,7,7,10,11,11] 输出: 10
解题
方法一：位运算
时间复杂度O(n),不符合题目要求
class Solution { public: int singleNonDuplicate(vector<int>& nums) { int res=0; for(int num:nums){ res^=num; } return res; } };
方法二：二分查找
class Solution { public: int singleNonDuplicate(vector<int>& nums) { nums.push_back(nums.back()+1);//添加一个元素使得总个数是2的倍数 int l=0,r=nums.size()/2-1;//组的个数有n / 2个 while(l<r){ int mid=(l+r)>>1; if(nums[mid*2]==nums[mid*2+1]) l=mid+1;//相等说明分界点在右边区间 else r=mid; //不相等说明分界点在左边区间 } return nums[l*2]; } };
