一列已經(jīng)排序的list，其中除了一個(gè)數(shù)只出現(xiàn)一次，別的數(shù)都出現(xiàn)恰好兩次，求如何用O(1)空間復(fù)雜度和O(logn)時(shí)間復(fù)雜度內(nèi)找出這個(gè)數(shù)，看這個(gè)復(fù)雜度就知是二分，具體思路有參考Discussion: https://leetcode.com/problems/single-element-in-a-sorted-array/solutions/3212178/day-52-binary-search-easiest-beginner-friendly-sol/?orderBy=hot
1 #540
2 #Runtime: 134 ms (Beats 72.61%)
3 #Memory: 20.6 MB (Beats 26.56%)
4
5 class Solution(object):
6 def singleNonDuplicate(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: int
10 """
11 l = 0
12 r = len(nums) - 1
13 while l < r:
14 mid = (l + r) // 2
15 if mid % 2:
16 mid -= 1
17 if nums[mid] == nums[mid + 1]:
18 l = mid + 2
19 else:
20 r = mid
21 return nums[l]