leetcode540

这道题目的要求，Note: Your solution should run in O(log n) time and O(1) space.

因此应该用二分查找的方式，代码如下：

 1 class Solution:
 2     def singleNonDuplicate(self, nums: 'List[int]') -> int:
 3         l = 0
 4         h = len(nums)-1        
 5         while l<h:
 6             m = l + (h-l)//2
 7             if m%2==1:
 8                 m-=1
 9             if nums[m] == nums[m+1]:
10                 l = m+2
11             else:
12                 h = m
13         return nums[l]

52ms，13.8mb

传统的方式，就是已经两次遍历，先遍历一遍数组，记录每一个值出现的次数，存储到一个字典中。

然后再遍历一次字典，找到只出现一次的那个值，代码如下：

1 class Solution:
2     def singleNonDuplicate(self, nums: 'List[int]') -> 'int':
3         count = {}
4         for num in nums:
5             count[num] = count.get(num, 0)+1  
6         for key in count:
7             if count[key] == 1:
8                 return key

48ms，14.5mb

这种方式想法很简单也很容易懂，但是需要额外的空间。但奇怪的是其执行时间却比二分查找的要快，感觉可能是测试集的样本问题。

还有一种技巧性比较强的方式，空间复杂度满足要求，但是时间复杂度应该更高：

1 class Solution:
2     def singleNonDuplicate(self, nums: 'List[int]') -> 'int':
3         res = nums[0]
4         for i in range(1,len(nums)):
5             res ^= nums[i]
6         return res

60ms，14mb

最后贴上三种方法的执行结果，从上倒下分别是第三种，第二种和第一种，这种不对称就是破除强迫症的排版（其实是我比较懒）