136. 只出现一次的数字 [easy]

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

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

说明：

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

示例 1:

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

示例 2:

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

通过次数231,901 | 提交次数335,747

23万次成功提交，这已经是编号一百多的题目了，有多少人在刷题啊。。。

Second Try

2020-07-03

看题解才了解到的，异或满足交换律啊，牛逼

看了知乎解释，异或可以理解为对覆盖的地方取反色，因此不在乎先后

如何理解「异或」的含义？ - 匡世珉的回答 - 知乎 https://www.zhihu.com/question/31116687/answer/50728074

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 异或满足交换律啊，牛逼
        # 看了知乎解释，异或可以理解为对覆盖的地方取反色，因此不在乎先后
        start = nums[0]
        for n in nums[1:]:
            start = start ^ n
        return start

执行用时：28 ms, 在所有 Python 提交中击败了58.01%的用户
内存消耗：13.9 MB, 在所有 Python 提交中击败了21.43%的用户

First Try

2020-07-03

其实空间复杂度不满足要求

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        counter = collections.defaultdict(int)
        for n in nums:
            counter[n] += 1
        return min(((v, k) for k, v in counter.items()))[1]

执行用时： 24 ms , 在所有 Python 提交中击败了 76.75% 的用户内存消耗： 15.3 MB , 在所有 Python 提交中击败了 7.14% 的用户

136. 只出现一次的数字 [easy]​

Second Try​

First Try​

136. 只出现一次的数字 [easy]

Second Try

First Try