interviewalgo
, , ,
Source
Edit
History

41. 缺失的第一个正数

Introduction

Question: 41. 缺失的第一个正数

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

 

进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

 

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

 

提示：

  • 0 <= nums.length <="300
  • -231 <= nums[i] <="231 - 1

解法一

Analysis

由于输入长度最大才到300，所以确实的第一个正数一定在1到300之间，所以可以直接用一个长度为300的bitset来做，遍历数组，遇到1到300之间的元素则插入，由于bitset长度固定了，所以空间复杂度也是O(1)，而且使用bitset的话，也就300/8=38字节。

有点作弊的感觉。。。

Implement

1
2
3
4
5
6
7
8
9
10
11
int firstMissingPositive(vector<int>& nums) {
    // nums 的个数最大才到 300，直接一个个判断是否出现，时间复杂度为`O(300*n)`
    bitset<301> b;
    for(int i: nums) {
        if (i >= 0 && i < 301) b.set(i);
    }
    for(int i = 1;i < 301;i++) {
        if (!b[i]) return i;
    }
    return 301;
}

解法二

Analysis

同样是利用第一个缺失的正数只可能是1到n，但这次是利用输入数组来替换掉前面的bitset。把所有在1到n的元素e放到nums[e-1]去，然后在遍历一次找到第一个nums[i] != i + 1的i，返回i+1即可。

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for(int i = 0;i < n; i++) {
        if (nums[i] > 0 && nums[i] <= n && nums[i]-1 != i && nums[i] != nums[nums[i] - 1]) {
            swap(nums[i], nums[nums[i]-1]);
            i--;
        }
    }
    for(int i = 0;i < n;i++) {
        if (nums[i] != i+1) return i+1;
    }
    return n + 1;
}