Leetcode-041-缺失的第一个正数

Leecode-041-First Missing Positive

思路：自哈希

题目描述

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

示例 1:

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

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

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

<!--more-->

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

做完本题，请继续做以下题目

Leetcode–041 : https://leetcode-cn.com/problems/first-missing-positive/

Leetcode–442 : https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/

Leetcode–448 : https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/

Solution：

参考题解：[leetcode-041][https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/]

我们来循序渐进的看这个问题

方法一：哈希表

话在前头：此方法空间复杂度不符合要求

• 按照刚才读题的思路，其实我们只需要从最小的正整数1开始，依次判断2，3，4直到数组长度N是否在数组中。
• 如果当前考虑的数不在这个数组中，我们就找到了这个最小正整数。
• 由于我们需要依次判断某一个正整数是否在这个数组中，我们可以先把这个数组中所有的元素放进哈希表。接下来在遍历的时候，就能以O(1) 的时间复杂度判断某个正整数是否在这个数组中。
• 由于题目要求我们只能使用常数级别的空间，而哈希表的大小与数组的长度是线性相关的，因此空间复杂度不符合题目要求。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;

        Set<Integer> set = new HashSet<>();

        // 遍历一遍数组，全部都放进去
        for (int num : nums) {
            set.add(num);
        }

        // 再遍历一遍set，如果不存在就说明找到了那个正数
        for (int i = 1; i <= len; i++) {
            if (!set.contains(i)){
                return i;
            }
        }

        // 极端情况下是最后一个元素
        return len + 1;
    }
}

• 时间复杂度：O(N) 这里 N 表示数组的长度。
• 空间复杂度：O(N) 把 N个数存在哈希表里面，使用了 N个空间。

方法二：排序 + 二分查找

话在前头：这个方法时间复杂度不符合要求

• 根据刚才的分析，这个问题其实就是要我们查找一个元素，而查找一个元素，如果是在有序数组中查找，会快一些；
• 因此我们可以将数组先排序，再使用二分查找法从最小的正整数 1 开始查找，找不到就返回这个正整数；
• 这个思路需要先对数组排序，而排序使用的时间复杂度是 O(NlogN)，是不符合这个问题的时间复杂度要求。

class Solution{

    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        // 排序时间复杂度O(NlogN)
        Arrays.sort(nums);

        // 二分查找去查找每一个正数
        // 二分查找时间复杂度O（logn）
        for (int i = 1; i <= len; i++) {
            // 一个一个去找
            int res = binarySearch(nums, i);
            // 如果没找到这个数，说明就是缺少的最小正整数
            if (res == -1) {
                return i;
            }
        }
        return len + 1;
    }


    // 常用二分查找模板
    private int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            // JDK源码中就是这么写的
            int mid = (left + right) >>> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

方法三：自哈希

所以自哈希 ：也就是将数组自身视为哈希表

• 我们可以把原始的数组当做哈希表来使用，事实上，哈希表本身其实也是一个数组。

• 我们要找的数就在 [1, N + 1] 里，最后 N + 1 这个元素我们不用找。因为在前面的 N 个元素都找不到的情况下，我们才返回 N + 1；

• 那么我们采用这样的思路

  • 1 这个数 放到下标是0的位置
  • 2 这个数 放到下标是1的位置
  • 。。。
  • 按照这个思路整理一遍数组

• 然后我们再遍历一次数组，第一个遇到它的值不等于下标的那个数，就是我们要找的确实的第一个正数。

• 这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值是 i 的数映射到下标为 i-1 的位置

class Solution{
    public int firstMissingPositive(int[] nums){
        int len = nums.length;

        // 对数组自己做哈希：数值为i的数字映射到下标 i - 1的位置
        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]){
                // 满足在指定范围内，并且没有放在正确的位置上，才交换
                // 例如：数值3应该放在索引2的位置上
                swap(nums,nums[i] - 1,i);
            }
        }

        // 遍历数组找到缺失的最小正数
        // 缺失的正整数是下标 + 1（i 从0 开始）
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1){
                return i + 1;
            }
        }

        // 都正确范围数组长度 + 1
        return len + 1;
    }

    // 交换函数
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

复杂度分析

• 时间复杂度：O(n)
  • while循环不会每一次都把数组里面的所有元素过一遍。如果有一些元素在这一次循环中被交换到他们应该在的位置上，那么在后序的遍历中，由于他们已经在正确的位置上了，代码执行到他们的时候，就会被跳过（相当于是一个剪枝的处理）
  • 最极端的一种情况是，在第 1 个位置经过这个 while 就把所有的元素都看了一遍，这个所有的元素都被放置在它们应该在的位置，那么 for 循环后面的部分的 while 的循环体都不会被执行。
  • 平均下来，每次元素只要被看一次就可以了。while 循环体被执行很多次的情况不会发生。这样的复杂度分析的方法叫做均摊复杂度分析。
• 空间复杂度：O(1)

打赏