欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

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

时间:2023-05-27
540、有序数组中的单一元素(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)}

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。