First Missing Positive

2015-09-30

问题描述

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 \(\Theta(n)\) time and uses constant space.

思路

方法一：

由于时间要求是\(\Theta(n)\)，所以不能采用排序算法，我最先想到的是利用hash table来辅助求解。时间上能满足要求，空间的要求是\(\Theta(n)\)，似乎有些不符合题意。

方法二：
可以利用已经给出的nums数组，用其数组的下标作为标记，而用数组元素的值作为hash函数的key。这样就不需要申请额外的空间了，可以直接在nums数组上做hash操作。但是nums数组的值被改变了。

Code

方法一代码：

int firstMissingPositive(vector<int>& nums) {
        unordered_map<int, bool> m;
        int i;
        int cnt = 1;
        int n = nums.size();
        if (n == 0) return 1;
        
        for (i = 0; i < n; i++){
            if (nums[i] > 0 && m.find(nums[i]) == m.end()){
                m[nums[i]] = true;
            }
        }
        
        while(m.find(cnt++) != m.end());
        
        return --cnt;
        
}

方法二代码：

其中注意一些细节的处理：

nums数组预先push_back(0)
对于负数和大于n的数，将其置为0
找first missing positive时，从数组的下标1开始找

int firstMissingPositive(vector<int>& nums) {
        int i;
        int n = nums.size();
        if (n == 0) return 1;
        //将数组长度加一，方便后续操作
        nums.push_back(0);
        //n比原来大了1
        n = nums.size();
        for (i = 0; i < n; i++){
            if (nums[i] < 0 || nums[i] >= n){
                nums[i] = 0;
            }
        }
        
        for (i = 0; i < n; i++){
            nums[nums[i] % n] += n;
        }
        //从下标1开始
        for (i = 1; i < n; i++){
            if (nums[i] / n == 0){
                return i;
            }
        }
        
        return n;
}