[多少懂点位运算】续·一行代码解决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 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

聊聊FilterSecurityInterceptor

本文就来研究一下spring security的FilterSecurityInterceptor

481
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

702
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

5866
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9664
来自专栏ml

md5算法原理一窥(其一)

    首先,需要了解的事,md5并不是传说中的加密算法,只是一种散列算法。其加密的算法并不是我们说所的那样固定不变,只是一种映射的关系。 所以解密MD5没有现...

3887
来自专栏菩提树下的杨过

linq to sql取出随机记录/多表查询/将查询出的结果生成xml

在手写sql的年代,如果想从sqlserver数据库随机取几条数据,可以利用order by NewId()轻松实现,要实现多表查询也可以用select * f...

2196
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

761
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2478
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1152
来自专栏封碎

Android中Broadcast的Intent大全 博客分类: Android小技巧 Android.netWAPGoogle

952

扫码关注云+社区