给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 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)}