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

点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

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

作者 | 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 的对应关系来辅助求解。

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

有热门推荐👇


1.程序员全球最厉害的 14 位程序员

2.【GitHub我在 GitHub 上看到了一个丧心病狂的开源项目!

3.【算法动画:七分钟理解什么是KMP算法

4.【数据结构十大经典排序算法动画与解析,看我就够了!


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

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 数组特性的妙用!如何找到「缺失的第一个正数」

我还会在以下平台发布内容

GitHub 哔哩哔哩