[多少懂点位运算】续·一行代码解决LeetCode268缺失数字

之前讲了利用位运算解决寻找唯一数字的问题，今天给大家展示一下另一个例子。

题目描述

268.缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

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

示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明: 你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

分析

这个题目是寻找在一个连续范围内没有出现过的一个数字，稍加变动就变成了和寻找唯一数字一样的问题——那就是在序列中再加上从0到n这n的数，之前没有出现的数字就只出现了一次，其他数字出现了两次，这样就可以一路异或过去了。

[3, 0, 1] => [3, 0, 1, 0, 1, 2, 3] => 2

代码实现

利用enumerate枚举，我们可以得到0到n - 1的序列号和这n - 1个数字。

利用reduce操作实现标题描述的一行代码解决问题。

from functools import reduce
class Solution:
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return reduce(lambda x, pair: x ^ pair[0] ^ pair[1], enumerate(nums), len(nums))

结语

这是一个难得的稍加变动变得和之前的题目一模一样的问题。

祝大家享受生活，享受代码。