凌云的博客

LeetCode 算法题 41. 缺失的第一个正数

分类：algorithm| 发布时间：2016-10-08 14:45:00

---

题目

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

示例 1:

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

示例 2:

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

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

说明:

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

解法 1

先对数组进行排序，再找出缺失的数字，由于排序算法时间复杂度并不是 O(n)， 因此这种解法并不符合题意。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int positive = 0;
        for (int i: nums) {
            if (i > 0) {
                if (i != positive && i != positive + 1) {
                    break;
                }

                positive = i;
            }
        }

        return positive + 1;
    }
};

解法 2

先将数字移到合适的位置（比如 1 移到下标为 0 的位置，2 移到下标为 1 的位置）再进行检查。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        const int n = nums.size();
        for(int i = 0; i < n; ++ i)
            while (nums[i] > 0 && nums[i] != i+1 && 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;
    }
};

解法 3

使用哈希表，这种方法不符合使用常量空间的要求。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_map<int,int> mp;
        const int size = nums.size();
        for(int i = 0; i < size; i++)
            if(nums[i] > 0 && nums[i] <= size)
                mp[nums[i]] = 1;

        int result = 1;
        for (int i = 1;i <= nums.size() + 1; i++) {
            if (!mp[i]) {
                result = i;
                break;
            }
        }

        return result;
    }
};