专栏首页算法channel我分析的一道笔试题,留言说说你是否看懂了?

我分析的一道笔试题,留言说说你是否看懂了?

今天分析一道题:找到重复值和错误值

1 首先看题目

集合 S 包含从1到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个元素复制了成了集合里面的另外一个元素的值,导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。

示例 1:

输入: nums = [1,2,2,4]

输出: [2,3]

注意:

给定数组的长度范围是 [2, 10000]。给定的数组是无序的。

链接:https://leetcode-cn.com/problems/set-mismatch ”

2 这是一类很具特色的数组

数组的取值范围:

1\leq nums[i]\leq n

其中,数组nums长度为n

这类数组特点鲜明,能够支持两种索引方法。

一种我们是熟知的线性访问方法:0len(nums)-1或者逆序:

nums = [4,2,3,1] # 取值严格控制在:[1,len(nums)]
for i in range(len(nums)):
    key = i
    print(nums[key],end=" ") # 4 2 3 1

另一种,就是它的特色访问方法,支持通过下面极具特点的方式:

nums = [4,2,3,1]
for i in range(len(nums)):
    key = nums[i]-1
    print(nums[key],end=" ") # 遍历结果 1 2 3 4 

访问数组的key等于元素值减去1

以后遇到满足取值满足

1\leq nums[i]\leq n

的这类数组,记住要联想到第二种访问方法,很多技巧都是基于这种访问方式。

3 详细分析过程

本题错误数据基于此种索引访问方法,能够精巧的求解,从而得到一个空间复杂度为O(1)的解,这太难能可贵了。

我看有的星友写出的解通过set集合方法,得到重复值,实际上set函数返回一个占用O(n)空间复杂度的对象,它不是更高效节省内存的解法。

下面分析怎么利用以上索引访问方法求解此题,原数组存在一对重复值,其他值都是唯一的。假定nums[i] 是重复值,则键 key 等于 nums[i] - 1 必然只存在一对重复值,其他值都唯一。

nums[key] 被遍历到后,我们乘以-1以此标记被访问到,因为key只有一对重复值,所以当第一次接触到这个key值时,我们标记nums[key]为负,再次接触到这个key值时,唯独nums[key]才能小于0,其他的key都不重复,所以再被标记为负值前都为正值,且以后再也没有机会被遍历到。

结论:满足 nums[key] < 0 时,key就是一对重复键,而key又等于abs(nums[i]) - 1,所以重复值为:abs(nums[i]) + 1.

找到重复值后,也就是我们只解码了一对重复key值的其中一个。

试想如果数组无错误,选用key = nums[i]-1遍历数组时,那么数组中所有元素都会被标记为负值。但是出现一对重复后,就会出现两个相等的key值,从而必然一个元素值无法被标记为负,拿个例子演示下:

再次被标记,但是不再乘以-1

可以看到元素5未被标记,根据key值与元素值的映射关系: key = nums[i]-1, val = nums[key],元素5的key0,所以nums[i] 等于key+1,即为 1,所以错误被标记的值为1。

再验证下,如果1未被错误标记,则key等于key 等于 1-1,即 nums[0]能被标记为负数,所以验证通过。

4 代码

理解以上后,很自然的就会写出下面的代码:

class Solution(object):
    def findErrorNums(self, nums):
        r = [0,0]
        for i,num in enumerate(nums):
            key = abs(num) - 1 # 减1防止越界,同时利用寻找重复值的特点来设计键
            val = nums[key] 
            if val < 0: # 只有找到重复值时,条件才会满足
                r[0] = key + 1
            else:       
                nums[key] = -val # 数组取值范围[1,n],用乘以-1标记被访问过
        
        for i,num in enumerate(nums): # 此时nums中只有一个值大于0,就是那个错值
            if num > 0: 
                r[1] = i + 1
        return r 

《end》

本文分享自微信公众号 - Python与机器学习算法频道(alg-channel),作者:振哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python|继承,多态,鸭子类型

    01 继承 编写一个类 class Animal(object): def shout(self): print('Animal i...

    double
  • Python 求中心索引,第二种方法不可取!

    今天,我们做一道 LeetCode 题目,开启咱们 【算法刷题日记】知识星球的第一道 LeetCode 题。题目的基本类型是 数组,考察点数组的索引、求和等,基...

    double
  • Python传奇:30年崛起之路

    作者 | 宋天龙,大数据技术专家,触脉咨询合伙人兼副总裁,前Webtrekk中国区技术和咨询负责人(Webtrekk,德国的在线数据分析服务提供商)。擅长数据挖...

    double
  • vue的表格动态渲染

    用户4344670
  • 原 前后端密钥分配验证

    Pulsar-V
  • 手把手的Numpy教程【一】

    当当当,我又开新坑了,这次的专题是Python机器学习中一个非常重要的工具包,也就是大名鼎鼎的numpy。

    TechFlow-承志
  • 小白博客 反弹shell 在公网服务器执行 nc –lvv 8888

    Lua采用了基于垃圾收集的内存管理机制,因此对于程序员来说,在很多时候内存问题都将不再困扰他们。然而任何垃圾收集器都不是万能的,在有些特殊情况下,垃圾收集器是...

    奶糖味的代言
  • Lua table之弱引用

    Lua采用了基于垃圾收集的内存管理机制,因此对于程序员来说,在很多时候内存问题都将不再困扰他们。然而任何垃圾收集器都不是万能的,在有些特殊情况下,垃圾收集器是无...

    晚晴幽草轩轩主
  • 微软拥抱Python:Anaconda现已包含Visual Studio Code

    IT派 - {技术青年圈} 持续关注互联网、区块链、人工智能领域 微软近日在官方博客宣布,已与与Anaconda达成合作,微软免费和跨平台代码编辑器 Vis...

    IT派
  • python之python-docx编辑和读取word文档

    如果是想读取其中的图片或是更复杂地编辑,首先我们需要先来认识下docx文档的格式组成:

    菲宇

扫码关注云+社区

领取腾讯云代金券