【LeetCode】136、只出现一次的数字

136、Single Number只出现一次的数字

难度：简单

题目描述

英文：

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
中文：

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

说明：

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

示例

Example 1:

1 2	Input: [2,2,1] Output: 1

Example 2:

1 2	Input: [4,1,2,1,2] Output: 4

解题思路

思路一

只有一个元素只出现一次，其余元素都出现两次，所以可以先对原数组去重并求和，再用两倍的和减去原数组的和，得到的结果就是只出现一次的元素值。

只适合只有一个元素次数不同的情况，且使用了额外空间。

代码提交

Python2，用时44ms，内存12.6M

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return 2 * sum(set(nums)) - sum(nums)

思路二

利用位运算的异或操作，任何数字异或其自身都等于零，任何数字异或零还等于其本身。

题目只有一个元素出现一次，其余元素都出现两次，出现两次的元素异或结果都为零，剩余一个出现一次的元素，与零异或后结果还是其本身，也就是说对所有元素进行异或操作后，结果即为只出现一次的那一个元素值。

代码提交

Python2，用时44ms，内存12.2M

看提交情况，用时最短的代码也是这个思路，约24ms，所以用时可能也和其他一些系统随机因素有关系吧。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        temp = 0
        for i in nums:
            temp ^= i
        return temp