leetcode540

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

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

 class Solution:

     def singleNonDuplicate(self, nums: 'List[int]') -> int:

         l = 0

         h = len(nums)-1

         while l<h:

             m = l + (h-l)//2

             if m%2==1:

                 m-=1

             if nums[m] == nums[m+1]:

                 l = m+2

             else:

                 h = m

         return nums[l]

52ms，13.8mb

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

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

 class Solution:

     def singleNonDuplicate(self, nums: 'List[int]') -> 'int':

         count = {}

         for num in nums:

             count[num] = count.get(num, 0)+1

         for key in count:

             if count[key] == 1:

                 return key

48ms，14.5mb

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

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

 class Solution:

     def singleNonDuplicate(self, nums: 'List[int]') -> 'int':

         res = nums[0]

         for i in range(1,len(nums)):

             res ^= nums[i]

         return res

60ms，14mb

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