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

相关文章

来自专栏mathor

BFPRT算法

 首先将原数组分成5个一组,每组内进行排序,组间不排序,然后将每组的中位数取出再次进行上述操作,直到最后只能分成一组了,然后取出中位数,将这个中位数当作标尺进行...

812
来自专栏mySoul

设计模式-UML关系基础

1135
来自专栏Leetcode名企之路

【Leetcode】60. 第k个排列

给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1:

2772
来自专栏TensorFlow从0到N

讨厌算法的程序员 1 - 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生...

3384
来自专栏java一日一条

最快最简单的排序算法:桶排序

在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总...

961
来自专栏程序员叨叨叨

5.1 基本数据类型第 5 章 CG 数据类型

本章将着重介绍Cg语言中预定义的内置(built in)的、或称为基本(primitive)的数据类型。然后介绍可以用来声明对象的各类类型,主要是数组和结构类型...

1113
来自专栏ml

向前字典排序

          next_permutation算法对区间元素进行一次组合排序,使之字典顺序大于原来的排序,有如下两个使用原形,对迭代器区间[first,l...

2679
来自专栏python读书笔记

《python算法教程》Day3 - 递归递归简介代码示例

这是《python算法教程》的第3篇读书笔记。由于之前看书的效率太低了,所以拖了一个多星期才写第三篇读书笔记。这次主要简单总结一下递归(recursion)。 ...

2928
来自专栏架构之路

寻找第K元素的八大算法、源码及拓展

一、问题描述  所谓“第(前)k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第(前)k个数的问题。 第K大问题可以是现实问题,譬如竞价...

5136
来自专栏Android机动车

数据结构学习笔记——总述

数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。

671

扫码关注云+社区

领取腾讯云代金券