有序数组中的单一元素（2022-2-14）每日一练

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 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

提示:

1 <= nums.length <= 1050 <= nums[i] <= 105 解题思路

这道题长见识了！

^异或运算：同为0，异为1。0^3 = 3，3^3 = 0

还可以用来取奇偶2^1 = 3 4^1 = 5然后3^1 = 2 5^1 = 4，当与1异或时，他们是成对取奇偶的。

另外，还有一个特性；3^5^5 = 3

所以这道题就出现了时间复杂度为*O(log n)*的解法。

当mid索引为奇数，我们就通过异或去拿与他成对的偶数，看这两个位置上的值是否相等。相等就说明在此之前的数都是成对排列存在的，单一元素不存在于前半段，把左边缘重置为mid+1；如果不相等，说明单一元素就存在于前半段，把右边缘重置为mid。直到left == right，就找到了「单一元素」

当mid索引为偶数，也同样。我们就通过异或去拿与他成对的奇数，看这两个位置上的值是否相等。相等就说明在此之前的数都是成对排列存在的，单一元素不存在于前半段……（同上）

var singleNonDuplicate = function(nums) {
	let left = 0,right = nums.length-1
  	while(left < right){
  		let mid = left + right >> 1
  		//mid = (left+right)/2 | 0
  		if(nums[mid] == nums[mid ^ 1]) left = mid + 1
  		else right = mid
  	}
  	return nums[right]
}

其实不通过二分也可以AC，而且可能速度更快

遍历去异或每一个元素，相同的话就是0（而0^x = x），直到碰到单一元素；然后单一元素再被异或偶数次，他还等于他自己。

var singleNonDuplicate = function(nums) { 
	let ret = 0
 	for(let i = 0; i< nums.length;i++){
 	  ret =  ret ^ nums[i]
 	}
 	return ret
}

或者更简单

var singleNonDuplicate = function(nums) { 
	return nums.reduce((a,b)=> a^b)
}