First Missing Positive -- LeetCode

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开始的正整数，第一个没有在所给数组中出现的正整数。

因为是从1开始的，我们可以将数组中所有的正整数都移动到它的正确位置，当所有数字都移动完毕后，从头检查第一个没有出现在该出现位置上的正整数就是所求的数字。若所有的数都出现了，则所求的数字就是n + 1，所有数字后面的那个数字。

该算法因为所有数字都是移动到自己的正确位置，因此每个数字都只会被移动一次。复杂度因此是O(n)。

所给数组中如果出现了重复的数字也不要紧，因为随着交换，所有正整数都回到了自己的正确位置后，重复数字会被交换到剩余的位置中去。而这些位置并不是他们的正确位置，因此也能指示出他们所处位置的正数缺失了。

 class Solution {

 public:

     int firstMissingPositive(vector<int>& nums) {

         int n = nums.size();

         for (int i = ; i < n; i++)

             while (nums[i] >  && nums[i] <= n && nums[nums[i] - ] != nums[i])

                 swap(nums[i], nums[nums[i] - ]);

         for (int i = ; i < n; i++)

             if (nums[i] != i + )

                 return i + ;

         return n + ;

     }

 };

巴特西

First Missing Positive -- LeetCode

最新文章

热门文章