41. First Missing Positive

 

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in  O ( n ) time and uses constant extra space.

 

这道题让我们找缺失的首个正数,由于限定了 O(n) 的时间,所以一般的排序方法都不能用,最开始博主没有看到还限制了空间复杂度,所以想到了用 HashSet 来解,这个思路很简单,把所有的数都存入 HashSet 中,然后循环从1开始递增找数字,哪个数字找不到就返回哪个数字,如果一直找到了最大的数字(这里是 nums 数组的长度),则加1后返回结果 res,参见代码如下:

 

解法一:

// NOT constant space
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int res = 1, n = nums.size();
        while (res <= n) {
            if (!st.count(res)) return res;
            ++res;
        }
        return res;
    }
};

 

但是上面的解法不是 O(1) 的空间复杂度,所以需要另想一种解法,既然不能建立新的数组,那么只能覆盖原有数组,思路是把1放在数组第一个位置 nums[0],2放在第二个位置 nums[1],即需要把 nums[i] 放在 nums[nums[i] - 1]上,遍历整个数组,如果 nums[i] != i + 1, 而 nums[i] 为整数且不大于n,另外 nums[i] 不等于 nums[nums[i] - 1] 的话,将两者位置调换,如果不满足上述条件直接跳过,最后再遍历一遍数组,如果对应位置上的数不正确则返回正确的数,参见代码如下:

 

解法二:

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/41

 

类似题目:

Missing Number

Find the Duplicate Number

Find All Numbers Disappeared in an Array

Couples Holding Hands

 

参考资料:

https://leetcode.com/problems/first-missing-positive/

https://leetcode.com/problems/first-missing-positive/discuss/17071/My-short-c++-solution-O(1)-space-and-O(n)-time

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation