之前讲了利用位运算解决寻找唯一数字的问题,今天给大家展示一下另一个例子。
给定一个包含 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))
这是一个难得的稍加变动变得和之前的题目一模一样的问题。
祝大家享受生活,享受代码。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。