Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Follow up: Your solution should run in O(log n) time and O(1) space.

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

分析:

一开始无从下手,虽然知道是二分法,但是不知道怎么用。

看了提示发现要找到独立数出现前后,奇数偶数位的变化。

【1,1,3,3】

独立数出现前,相同数字的index为:偶,奇,偶,奇

【1,1,2,3,3】

独立数出现之后,变为了 偶,奇,独,奇,偶。

所以根据这个变化在二分的时候判断独立数是在左边还是在右边。

Solution:

def singleNonDuplicate(self, nums):
“””
:type nums: List[int]
:rtype: int
“””
if not nums: return None
if len(nums) == 1:
return nums[0]

i, j = 0, len(nums)-1

while i < j:
mid = i + (j-i)/2
if nums[mid] != nums[mid-1] and nums[mid]!=nums[mid+1]:
return nums[mid]
elif nums[mid] == nums[mid+1]:
if mid % 2 == 0:
i = mid + 2
else:
j = mid — 1
else:
if mid % 2 == 0:
j = mid — 2
else:
i = mid + 1

return nums[j]

看到一个大神的解法:

def singleNonDuplicate(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) / 2
if nums[mid] == nums[mid ^ 1]:
lo = mid + 1
else:
hi = mid
return nums[lo]

挺有意思的:

odd xor 1 == odd — 1

even xor 1 == event + 1