题:给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
示例:
输入: nums = [1,1,2,3,3,4,4,8,8]输出: 2
解:看到题目 中O(log n) 时间复杂度,容易想到二分查找。难点是这题中不是查找某一个值,而是查找一个单独的数。条件 nums[mid] ?? target 要如何改变?
单独元素前面有n对元素,即2n个元素,所以单独元素的下标一定是偶数。对偶数下标二分搜索。
若它与num[mid+1]是一对,则说明前面的都是成对的,low= mid+2;否则说明前面有单独的,high = mid。
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
low, high = 0, len(nums) - 1
while low < high:
mid = (low + high) // 2
mid -= mid & 1
#mid -= mid & 1 作用是让mid取偶数。&是按位与,奇数&1 = 1,偶数&1 =0。
if nums[mid] == nums[mid + 1]:
low = mid + 2
else:
high = mid
return nums[low]
如果 while循环用 <= 条件,需要high 初始化为len(nums)-2,否则会数组越界。 搜索空间为[0,len(nums)-2],实际上mid最大取值len(nums)-2在区间内,所以有不会遗漏。
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
low, high = 0, len(nums) - 2
while low <= high:
mid = (low + high) // 2
mid -= mid & 1
if nums[mid] == nums[mid + 1]:
low = mid + 2
else:
high = mid-2
return nums[low]