Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
兩種方法：
- 位運(yùn)算
def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
for i in nums:
res ^= i
return res
- 二分法链韭，觀察哪邊是偶數(shù)煮落，切分開(kāi)來(lái)不相等：
def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
start = 0
end = len(nums)-1
while(start<end):
mid = (start+end)/2
'''L=[3,3,7,7,|10,11,11]；而[1,1,2,2,3,|4,4,8,8]'''
if mid%2 == 1:
mid -= 1
if nums[mid] == nums[mid+1]:
start = mid+2
else:
end = mid
'''如果一半正好是奇數(shù)旋讹，自減1這一半就是偶數(shù)轿衔，如果相等，那么這邊偶數(shù)的那一邊是不會(huì)出現(xiàn)這個(gè)單數(shù)胚股，如果不相等，那就是在這一側(cè)琅拌；如果一半是奇數(shù)，如果不相等进宝，那另一邊都是偶數(shù)則不會(huì)有這個(gè)單數(shù)，一定在自己這個(gè)奇數(shù)個(gè)的這邊党晋，如果相等，那就在另一邊灾而，因?yàn)橐粋€(gè)數(shù)不可能跟兩邊都相等'''
return nums[start]
