【LeetCode】41. First Missing Positive的解法及注释

向右看齐 2022-07-25 15:52 82阅读 0赞

41. First Missing Positive

Total Accepted: 62151 Total Submissions: 261770 Difficulty: Hard

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,200000\],\[-10001,123,100000\]，我看过网上的一些解法，采用的是“**桶排序**”的思想，但是考虑起来会比较复杂，这里我们采用**另外一种思路**来考虑问题：  
    1、由于我们只需要找到给定数组（数据集）中缺失的最小正整数即可，既然是正整数，那么负数和零就可以不予考虑；  
    2、既然是寻找缺失最小正整数，那么太大的数据，我们无需考虑，何为太大？超过给定数据集大小:nums.size()的数据无需考虑，这里需要解释一下：如果给定数据集大小nums.size()=N，如果这N个数据中有M个数数值大于N，如果我们把这些数排个序：a1,a2,a3,a4....a(N-M),b1,b2,b3,...bM；由于N<b1<=b2<=b3,...<=bM，那么数据集中在自然数区间\[1,N\]之间的数实际上只有N-M个，那么缺失的最小正整数一定在\[1,N\]中，这个缺失的最小正整数可能的最大值为a(N-M)+1。当M=0时，且给定数据集中数据为\[1,N\]的无重复自然数，此时，缺失的最小正整数最大值为N+1,其他情况下，只要给定数据集中存在小于1或者大于N的数据，那么缺失的最小正整数便一定存在于\[1,N\]即\[1,nums.size()\]之间。

根据上面的分析，我们可以采用类似“**哈希表**”的方法来求解，由于我们并不关心那些小于1和大于给定数据集长度N=nums.size()的数据，我们需要的“哈希表”空间最大为N；在遍历数据集中数据的时候，对于小于1和大于的数据，我们直接丢弃，对于\[1,N\]之间的数据i，我们移位至nums\[i-1\]（数组下标从零开始）。举例说明给定数据集\[-123,3,4,-1,1,1000\]，数据集大小为6，从第一个元素开始遍历，小于1和大于6的数据（-123，-1,1000）直接跳过，\[1,6\]之间的数据（1,3,4）分别移动到nums\[1-1\]，nums\[3-1\]，nums\[4-1\]中，明显nums\[1\]中的元素必然不等于1+1，我们队换位后的数组进行一次遍历，便可迅速找到它，时间复杂度为O(n)，无需额外空间，具体见程序。

【解法】

class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            
            int i = 0;
            //遍历给定数据集，我们只关心[1, nums.size()]范围的数据，如果它们没有在期望的位置，则移动到对应位置
            while (i < nums.size())
            {
                if (nums[i] != (i+1) && nums[i] >= 1 && nums[i] <= nums.size() && nums[nums[i]-1] != nums[i])
                    swap(nums[i], nums[nums[i]-1]);//不在期望位置则移动至期望位置，移动后辗转移动
                else                               //nums[nums[i]-1]==nums[i]时，即存在重复数字，已经占位，不再移动
                    i++;//区间外的数据不必考虑
            }
            for (i = 0; i < nums.size(); ++i)//再次遍历，寻找空缺值
                if (nums[i] != (i+1))//第一个缺失值即为最小空缺正整数
                    return i+1;
            return nums.size()+1;//如果给定数据集数据无重复，且均在[1, nums.size()]，那么最小正整数为N+1
        }
    };