当前位置：首页 > article >正文

【算法】【数组与矩阵模块】求数组中从未出现的最小正整数（含拓展思路）

article 2024/9/20 5:49:59

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定数组arr，求数组中从未出现的最小正整数
如：arr = [-1,3,4,5]
结果为0
要求空间复杂度为O（1），时间复杂度O(n)

解决方案

原问题：
1、申请两个变量l和r，作为arr的左右游标
2、遍历arr，如果arr[l] = l + 1,说明arr[l]在理想的位置，l++
3、否则如果 arr[l] <= l 或者arr[l] > r 或者 arr[arr[l] - 1] = arr[l]（这个出现过的值已经在理想的位置上了），r–,arr[l] = arr[r]
4、如果不满足2和3，则说明arr[l]还在范围之中，只不过没有遍历到而已，将arr[l]放到应该去的地方
5、直到l=r，遍历结束，返回l+1即可

代码编写

java语言版本

原问题：
方法一:

  /**
     * 二轮测试：计算数组中未出现的最小正整数
     * @param arr
     * @return
     */
    public static int getMissNumCp1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        // 期望arr = [1,2,3,4,5,6...]，l代表截止目前已经存在的范围[1,l],r代表截止目前，后面无论多么理想，范围最优[1...r]
        int l = 0, r = arr.length;
        while (l < r) {
            if (arr[l] == l+1) {
                // arr[l]在理想的位置
                l++;
            }else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {
                // arr[l]不在期望的区间内，或者在期望区间内但是不在当前位置
                // 期望的范围-1，因为出现了期望之外的值或者有重复值
                r--;
                arr[l] = arr[r];
            }else{
                // 出现了期望的值，但是不在应该在的位置上
                CommonUtils.swap(arr, l, arr[l] - 1);
            }
        }
        return l + 1;
    }


    public static void main(String[] args) {
        System.out.println(getMissNumCp1(new int[]{-1,2,3,4}));
    }

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题如果不限制空间，用统计法瞬间就能解决。
这道题如果不限制时间，排个序再遍历一下瞬间就能解决。
但是。。。时间和空间都在最小的范围内解决这道题的办法，其实还是比较经得起推敲的
首先我们要真的理解r和l两个游标的含义，我们要求的是数组中从未出现过的正整数，关键词在于正整数，这跟l初始化为0是紧密关联的，可不是因为arr的起始坐标为0而设计的，l存在的意义就是为了遍历中验证在arr中l+1这个值出现过没有？
我们可以这么理解，理想情况下arr=[1,2,3,4,5,6,…]，最小正整数如果存在，那么整个数组中小于正整数的数必须会存在，否则它就不是最小正整数了，并且最小正整数一定会存在于[1,2,3,4,5…arr.len]。那么现在遍历l，我们先判断是否是理想情况，如果是的那么l++，很好理解，当遇到不是理想的情况时，当前的值可能有几种情况呢？1、这个数应该在的坐标arr[l]-1超出了理想的范围，（ (-∞, l）∪（r，+∞）），或者这个数已经在自己应该在的位置上了，重复，所以有这个条件 arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]，这种情况下说明整个数组的候选者范围减小，因此当前值应该和arr[r]交换（这里因为当前值坑定不是最小值了，所以使用了直接覆盖的方式）,之后r–。
2、这个数如果没有出界，说明了这个数还在[l…r]之间，只不过没有到它应该在的位置上，这个时候将这个数和它应该在的位置上的值进行一个交换（这里呼应了为什么要判断一下是否存在重复，否则这里会死循环）
这道题理解起来其实比较费劲，整个过程类似于遍历坐标，然后找这个坐标上的值是否应该在它应该在的位置上，如果不在的话是否在范围中，如果也不在，则整个范围就会减小，最小值不会超过r