41. First Missing Positive 分析

男娘i 2022-05-24 02:17 93阅读 0赞

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.

*  限定了时间复杂度和空间复杂度
 *  一开始只能想到先排序再遍历找到第一个不连续的正整数部分的起点就可以了，但是排序都需要nlog(n)的时间复杂度，并不能满足要求。
 *  是否需要将原始数组排序成为了一个分水岭，也是这道题的区分度所在。

> 解法：

*    
    
 *  采用交换元素的方式，将数组下标与数组元素大小对应起来。

> 假设数组的大小为n，我们遍历整个数组，如果当前元素i在1-n之间那么就将当前元素和数组第i-1个元素交换。如果当前元素是复数或者大于n那么就不处理。  
> 这样遍历完所有的元素之后，原始数组当中出现在1-n之间的元素都被放在了对应的0~n-1的位置里。再次遍历数组，找到第一个不满足v\[i\]==i+1的位置，那么i+1就是最小的未出现的正整数。

## \- 关键点：利用数组的下标i表示1~n这n个数，如果数组当中出现了1~n之间的元素那么一次遍历将可以将这些元素放置在对应的位置。没有出现的元素对应位置的值一定就不满足v\[i\]==i+1，那么第一个出现的就是最小的！ ##

//找到一组无序的整型数组当中未出现的正整数当中最小的那个
    //使用o(n)的时间复杂度 和常数的空间
    //找到数组当中最小的整数值然后
    
    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int n = nums.size();
            if(!n) return 1;
    
            for(int i=0;i<n;++i) {
                if(nums[i]==i+1) continue;
                while(nums[i]<=n&&nums[i]>0&&nums[i]!=nums[nums[i]-1]) {
                    int temp = nums[nums[i]-1];
                    nums[nums[i]-1] = nums[i];
                    nums[i] = temp;
                }
            }
            int i = 0;
            for(i=0;i<n;++i) {
                if(nums[i]!=i+1)
                    break;
            }
            return i+1;
        }
    };