一列已經排序的list，其中除了一個數只出現一次，別的數都出現恰好兩次，求如何用O(1)空間復雜度和O(logn)時間復雜度內找出這個數，看這個復雜度就知是二分，具體思路有參考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]