LeetCode 136. Single Number 只出现一

链接

https://leetcode-cn.com/problems/single-number/description/

要求

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

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

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

相关代码

过程中前两次尝试均超出时间限制

# 方法1
class Solution(object):
    def singleNumber(self, nums):
        return [x for x in set(nums) if nums.count(x) == 1][0]

# 方法2
class Solution(object):
    def singleNumber(self, nums):
        for i in set(nums):
            if nums.count(i) == 1:
                return i

思路：
既然除目标数外均出现两次，那么用sorted排序后每隔两个取一个，就可以完美将重复数分开。之后再取两个列表的差集即可。

# 示例
x1 = [1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7]
x2 = x1[1::2]
x3 = x1[::2]

print x1
print x2
print x3
print set(x2) ^ set(x3)

# print结果
[1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7]
[1, 2, 3, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
set([4])

整理后代码如下(执行用时44 ms)

# 方法3
class Solution(object):
    def singleNumber(self, nums):
        nums = sorted(nums)
        return list(set(nums[1::2]) ^ set(nums[::2]))[0]