LeetCode--136--只出现一次的数字

问题描述：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

方法1：1 ^ 1 = 0 ,1 ^ 0 = 1

1 class Solution(object):
2     def singleNumber(self, nums):
3         """
4         :type nums: List[int]
5         :rtype: int
6         """
7         for i in range(1,len(nums)):
8             nums[0] ^= nums[i]
9         return nums[0]

方法2:字典法

 1     def singleNumber(self, nums):
 2         """
 3         :type nums: List[int]
 4         :rtype: int
 5         """
 6         res = {}
 7         for i in nums:
 8             if i in res:
 9                 res.pop(i)
10             else:
11                 res[i]=1
12         return list(res.keys())[0]

方法3：排序后比较大小

 1 class Solution(object):
 2     def singleNumber(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: int
 6         """
 7         nums.sort()
 8         for i in range(1,len(nums),2):
 9             if(nums[i]>nums[i-1]):
10                 return nums[i-1]
11         return nums[len(nums)-1]

2018-09-12 20:32:15