[多少懂点位运算】续·一行代码解决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))

结语

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

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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏胖胖的专栏

使用 trie 树实现简单的中文分词

导语:工作中偶尔遇到需要对中文进行分词的情况,不要求非常高的精确度和语境符合度,仅是为了统计某些词出现的热度。本文提供了一种简单易行的中文分词方法。 工作中,偶...

5625
来自专栏Hongten

python开发_python中的module

在python中,我们可以把一些功能模块化,就有一点类似于java中,把一些功能相关或者相同的代码放到一起,这样我们需要用的时候,就可以直接调用了

714
来自专栏数据结构与算法

08:Challenge 1

总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列,有M次操作,每次操作是以下两种之一: (1)...

29212
来自专栏程序员互动联盟

【编程基础】写代码,你应该知道九类规则

网上有太多讲编码规范、编码习惯的文章,但我总是念的多,实际去认真阅读理解的少。或多或少的按照自己的思维去编写代码。这种习惯让我吃大亏,比如一个指针未赋值导致偶尔...

3565
来自专栏xiaoxi666的专栏

【模板小程序】十进制大数相加(正整数版本+整数版本【正负0】),包含合法性检查

为适应于不同用途,将大数算法写成了两个版本,分别为只处理正整数的版本和包含负数处理的版本,可根据需要选用。

993
来自专栏xiaoxi666的专栏

【模板小程序】十进制大数相加(正整数版本+整数版本【正负0】),包含合法性检查

为适应于不同用途,将大数算法写成了两个版本,分别为只处理正整数的版本和包含负数处理的版本,可根据需要选用。

601
来自专栏程序员的SOD蜜

实例探究字符编码:unicode,utf-8,default,gb2312 的区别

 最近做邮件收发,不同的邮件系统间可能会出现编码问题,迫使我重新回来研究一下字符的编码问题,unicode,utf-8,gb2312这些编码格式都是我们熟知的,...

21210
来自专栏kalifaの日々

腾讯大连电话面试题目

1.项目相关的细节问题。 2.讲讲STL里你常用的数据结构 2.1那么map的时间复杂度是多少 2.2map的底层实现是什么 3.讲解MVC每一层分别是...

532
来自专栏owent

POJ PKU 2446 Chessboard 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2446

582
来自专栏嵌入式程序猿

号外号外:无规矩不成方圆(4)

本文MISRA规则由嵌入式程序猿整理自网络,版权归原作者所有 不能使用三字母词 三字母词由2 个问号序列后跟1 个确定字符组成(如, ??- 代表“ ~”(非)...

2555

扫码关注云+社区