凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 41. First Missing Positive

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


题目

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

For example,

Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

题意

给定一个无序的数组,找出第一个缺失的数字。

解法 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] <= 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;
    }
};