专栏首页五分钟学算法数组特性的妙用!如何找到「缺失的第一个正数」

数组特性的妙用!如何找到「缺失的第一个正数」

作者 | P.yh

今天分享的题目来源于 LeetCode 第 41 号问题:缺失的第一个正数。题目难度为 Hard。本文使用了一个比较 Trick 的解法。

题目描述

给定一个未排序的整数数组,找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]
输出: 3

示例 2:

输入: [3,4,-1,1]
输出: 2

示例 3:

输入: [7,8,9,11,12]
输出: 1

说明:

你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。

题目解析

给一个整形数组,找出最小缺失的正整数,例如 [0,-1,2] 中最小缺失的正整数就是 1,[ 1,2 ,4 ,9 ] 中最小缺失的正整数就是 3。

这道题如果不加上 O(n) 时间和 O(1) 空间这样的限定条件,应该再简单不过,但是加上了这两个要求,一下子使问题变得棘手。

怎么思考呢?

首先这道题给定的条件很有限,输入参数就 只有数组 ,如果非要用 O(n) 时间和 O(1) 空间来做的话,表示我们除了输入数组以外,不能借助任何其他的数据结构。

数组应该是属于一类最最基础的数据结构,除去 length 之外,就只有两个属性 indexvalue,那这道题就变成了 如何利用数组的 value 和 index 之间的关系来找到最小缺失正整数 ,如果想到了这一点,就已经成功了一半。

如果继续想下去有几点是可以明确的:

  1. 缺失的正整数肯定在 [1, array.length + 1] 这个范围内
  2. 我们可以交换输入数组中的元素的位置来让 index 和 value 的关系更加明确
  3. 保证 index 和 value 的关系后,我们可以通过 index 来判定整数的存在性

第一点很好理解,一个数组总共有 array.length 这么多个数,全部排满,也就是 1,2,…array.length, 那么答案就是 array.length + 1,没有排满,那么在这之间肯定是有缺失元素的。

第二点是说我们可以通过交换来让 index 和 value 形成对应,我们看的是 value,但是 index 可以辅助我们寻找。

前两点明确了,第三点就是从头到尾寻找答案的过程。

代码实现

public int firstMissingPositive(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 1;
    }

    for (int i = 0; i < nums.length;) {
        if (nums[i] <= 0 || nums[i] > nums.length || nums[nums[i] - 1] == nums[i]) {
            i++;
            continue;
        }

        // swap
        int tmp = nums[nums[i] - 1];
        nums[nums[i] - 1] = nums[i];
        nums[i] = tmp;
    }

    for (int i = 0; i < nums.length; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    return nums.length + 1;
}

总结

代码中 index 和 value 的对应关系是 index = value - 1,代码实现有两点需要注意。

  • 第一点,交换完后,需要判断交换过来的数是否需要被放到相应的地方,例如 [2,3,1]
  • 第二点,元素越界的话,以及元素 value 已经和 index 对应上了,那么就应该继续遍历,例如 [0,-1,1][1,1]

总的来说这道题并没有涉及什么算法和数据结构的应用,有点像脑筋急转弯的感觉,想到了就做的出,想不到的话就做不出,但是它给我们解数组问题提供了一个新的方向:利用 index 和 value 的对应关系来辅助求解。

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu)

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

原始发表时间:2019-09-19

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于HTML5 canvas的纯JS二维码生成

    qrious是一款基于HTML5 canvas的纯JS二维码生成插件。通过qrious.js可以快速生成各种二维码,你可以控制二维码的尺寸颜色,还可以将生成的二...

    用户5997198
  • 基础面试,为什么面试官总喜欢问String?

    关于 Java String,这是面试的基础,但是还有很多童鞋不能说清楚,所以本文将简单而又透彻的说明一下那个让你迷惑的 String

    用户4172423
  • 【整理分享】14张思维导图构建 Python 核心知识体系

    基础知识图一包括了基本规则、Python语言特点、计算机语言、如何运行Python、变量赋值五个方面,辅助你快速掌握Python编程的基底知识。

    1480
  • 一日一技:在 Python 中快速遍历文件

    实际上,要解决遍历文件的问题,只需要使用 Python 自带的 glob模块即可:

    青南
  • SQLmode最佳实践

    MySQL服务可以在不同的SQL模式下运行,并且可以针对不同的客户端以不同的方式应用这些模式,具体取决于sql_mode系统变量的值。我们可以设置全局SQL模式...

    MySQL技术
  • 一日一技:实现函数调用结果的 LRU 缓存

    在工程项目中,可能有一些函数调用耗时很长,但是又需要反复多次调用,并且每次调用时,相同的参数得到的结果都是相同的。在这种情况下,我们可能会使用变量或者列表来存放...

    青南
  • 单例模式的几种实现方式及对比

    单例模式是设计模式中最简单也是最常用的模式之一,所谓单例就是在系统中只有一个该类的实例。

    walking在cloud.tencent
  • 科学使用HBase Connection

    这个问题的答案简单而不简单:HBase客户端是不需要维护连接池的,或者说,Connection对象已经帮我们做好了。但是,对Connection使用不当是HBa...

    王知无
  • 机器学习在MVPD视频广告中的应用

    本文来自MHV (Mile High Video) 2019的演讲,作者是来自于Charter公司的Srilal Weera。本次演讲主要讲述了机器学习在视频分...

    用户1324186
  • LeetCode 二叉树问题小总结

    LeetCode 上面的二叉树问题一般可以看成是简单的深度优先搜索问题,一般的实现方式是使用递归,也会有非递归的实现方法,这边文章主要介绍一下解决二叉树问题的几...

    五分钟学算法

扫码关注云+社区

领取腾讯云代金券