【数据结构与算法】之深入解析“缺失的第一个正数”的求解思路与算法示例

举报
Serendipity·y 发表于 2022/02/16 22:05:23 2022/02/16
【摘要】 一、题目要求 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。示例 1: 输入:nums = [1,2,...

一、题目要求

  • 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
  • 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
  • 示例 1:
输入:nums = [1,2,0]
输出:3

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

  
 
  • 1
  • 2
  • 示例 3:
输入:nums = [7,8,9,11,12]
输出:1

  
 
  • 1
  • 2
  • 提示:
    • 1 <= nums.length <= 5 * 105
    • -231 <= nums[i] <= 231 - 1

二、求解算法

① 哈希表(空间复杂度不符合要求)

  • 本题的难点在:只能使用常数级别的额外空间,在这个限制下本题的思路有一个非正式的名称:原地哈希。
  • 其实我们只需从最小的正整数 1 开始,依次判断 2、 3 、4 直到数组的长度 N 是否在数组中;
  • 如果当前考虑的数不在这个数组中,我们就找到了这个缺失的最小正整数;
  • 由于我们需要依次判断某一个正整数是否在这个数组里,我们可以先把这个数组中所有的元素放进哈希表。接下来再遍历的时候,就可以以 O(1) 的时间复杂度判断某个正整数是否在这个数组;
  • 由于题目要求只能使用常数级别的空间,而哈希表的大小与数组的长度是线性相关的,因此空间复杂度不符合题目要求。
  • Java 示例:
import java.util.HashSet;
import java.util.Set;

public class Solution {

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

        Set<Integer> hashSet = new HashSet<>();
        for (int num : nums) {
            hashSet.add(num);
        }

        for (int i = 1; i <= len ; i++) {
            if (!hashSet.contains(i)){
                return i;
            }
        }

        return len + 1;
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

② 二分查找(时间复杂度不符合要求)

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

public class Solution {

    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);

        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) {
            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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33

③ 将数组视为哈希表

  • 由于题目要求「只能使用常数级别的空间」,而要找的数一定在 [1, N + 1] 左闭右闭(这里 N 是数组的长度)这个区间里。因此,我们可以就把原始的数组当做哈希表来使用。事实上,哈希表其实本身也是一个数组;
  • 要找的数就在 [1, N + 1] 里,最后 N + 1 这个元素不用找。因为在前面的 N 个元素都找不到的情况下,才返回 N + 1;
  • 那么,可以采取这样的思路:就把 1 这个数放到下标为 0 的位置, 2 这个数放到下标为 1 的位置,按照这种思路整理一遍数组。然后我们再遍历一次数组,第 1 个遇到的它的值不等于下标的那个数,就是要找的缺失的第一个正数。
  • 这个思想就相当于我们自己编写哈希函数,这个哈希函数的规则特别简单,那就是数值为 i 的数映射到下标为 i - 1 的位置。

在这里插入图片描述

  • Java 示例:
public class Solution {

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

        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, -1, 3, 4]
        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 index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • C++ 示例:
// author:rmokerone
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int firstMissingPositive(vector<int> &nums) {
        for (int i = 0; i < nums.size(); i++) {
            while (nums[i] != i + 1) {
                if (nums[i] <= 0 || nums[i] > nums.size() || nums[i] == nums[nums[i] - 1])
                    break;
                // 将nums[i] 放置到对应位置上[1,2,3...]
                int idx = nums[i] - 1;
                nums[i] = nums[idx];
                nums[idx] = idx + 1;
            }
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != (i + 1)) {
                return (i + 1);
            }
        }
        return (nums.size() + 1);
    }
};

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

文章来源: blog.csdn.net,作者:Serendipity·y,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/Forever_wj/article/details/122769807

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。