只出现一次的数字(Leetcode 136)

题目分析

  接下来的几天给小伙伴介绍一种新题型，当我看到这个题目的时候，我觉得很简单，但是往往面试或者笔试的时候，会对时间复杂度或者空间复杂度进行限制，让我们一起来康一康吧。

位运算

当然暴力求解很容易，用一个字典保存每一个值出现的次数即可。但是空间复杂度为O(n)，可不可以使用一种空间复杂度为O(1)的算法呢？位运算应运而生了，异或的特点是相同为0，那么两个相同的数字异或会得到0，0和x异或为x。如果所有的数都出现两次，那么将所有的数字异或的结果为0，如果只有一个数字出现了一次，那么异或的结果为该数字。

from functools import reduce


class Solution:
    def singleNumber(self, nums):
        return reduce(lambda x, y: x ^ y, nums)

刷题总结

  一个Pythonic的写法，只需要一行代码，非常简洁。妙啊~，位运算往往就是这样，难度可能并不大，但是不容易想到，那接下来让我们看一看难度较大的题目吧。