原题
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例1:
输入： [1,1,2,3,3,4,4,8,8] 输出： 2
示例2:
输入： [3,3,7,7,10,11,11] 输出： 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
解法
思想
最优解法：二分查找达到O(log n)时间复杂度。
保持数组个数为奇数（即永远只包含一个单一元素），每次取中间的元素，如果前面的元素与当前元素相等，又分两种情况：
- 前面的元素个数为偶数个，则除去选中本身的这一对，前面的元素个数为奇数个，说明单一元素出现在该元素前面，可以把要查找的结束位置指向当前元素对之前，在图中下一步指向2。
- 前面的元素个数为奇数个，则除去选中本身的这一对，前面的元素个数为偶数个，说明单一元素出现在该元素后面，可以把要查找的开始位置指向当前元素对之后，在图中下一步指向10。
如果当前元素和后面的元素相等情况也是类似的，可以逐一分析。
其他解法：暴力法，异或。
代码
二分查找：
class Solution {
public int singleNonDuplicate(int[] nums) {
int start = 0;
int end = nums.length-1;
while(start<end){
int mid = (start+end)/2;
if(mid%2==0) {
if(nums[mid-1]==nums[mid]) end = mid-2;
else if(nums[mid+1] == nums[mid]) start = mid+2;
else return nums[mid];
}else{
if(nums[mid-1]==nums[mid]) start = mid+1;
else if(nums[mid+1] == nums[mid]) end = mid-1;
else return nums[mid];
}
}
return nums[start];
}
}
暴力法：
class Solution {
public int singleNonDuplicate(int[] nums) {
for (int i = 0; i < nums.length - 1; i+=2) {
if (nums[i] != nums[i + 1]) {
return nums[i];
}
}
return nums[nums.length - 1];
}
}
异或：
class Solution {
public int singleNonDuplicate(int[] nums) {
int cur=0;
for (int i:nums) cur=cur^i;
return cur;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode540-%e6%9c%89%e5%ba%8f%e6%95%b0%e7%bb%84%e4%b8%ad%e7%9a%84%e5%8d%95%e4%b8%80%e5%85%83%e7%b4%a0/
