一列已经排序的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]