Leetcode——41. 缺失的第一个正数

这题是双指针不假，不过其更多的有快排的影子。

对于长度为 n 的数组，缺失的第一个正整数的范围为 [1, n + 1] ，因为，如果是数组是从1开始的严格递增数组，则答案为 n + 1 。

根据如上思考和题意，我们可以将每个数字放在一种对应的下标处，例如1放在0处、2放在1处。这样当我们整理好数组后，循环遍历，只需要 nums[i] != i + 1 时返回 i + 1即可。

现在问题是如何处理数组。考虑到答案在 [1, n + 1] 区间内，我们可以设置两个变量 l, r。

l 指向数组最左侧，r 指向数组溢出位置。有如下讨论：

①如果 nums[l] > r，则 swap(l, --r)        // 这样可以将无效数据放在数组末尾

②如果 nums[l] <= l, 则 swap(l, --r)

③如果 nums[l] == l + 1，则 l++

④如果 l + 1 < nums[l] <= r

        Ⅰ如果 nums[nums[l] - 1] == nums[l]， 则对应位置数字已存在，最为无效数据处理

                swap(l, --r)

        Ⅱ如果 nums[nums[l] - 1] != nums[l]，则对应位置数字未存在，放在指定位置

                swap(l, nums[l] - 1)

根据以上讨论完成代码即可。

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int l = 0, r = nums.size();while(l < r){if(nums[l] == l + 1){l++;}else{if(nums[l] > l + 1 && nums[l] <= r){if(nums[nums[l] - 1] != nums[l]){swap(nums, l, nums[l] - 1);}else{swap(nums, l, --r);}}else{swap(nums, l, --r);}}}for(int i = 0; i < nums.size(); ++i){if(nums[i] != i + 1){return i + 1;}}return nums.size() + 1;}void swap(vector<int>& nums, int i, int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
};

本题的交换思想在很多地方都会用到，尤其是快排，并且这里将数字与数组下标对应起来也是一种哈希表的思想。

补：最后遍历数组实际上是多余的，由于双指针的策略，最终 l 所指位置应填的数是注重找不到的，所以返回 l + 1 即可。

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int l = 0, r = nums.size();while(l < r){if(nums[l] == l + 1){l++;}else{if(nums[l] > l + 1 && nums[l] <= r){if(nums[nums[l] - 1] != nums[l]){swap(nums, l, nums[l] - 1);}else{swap(nums, l, --r);}}else{swap(nums, l, --r);}}}return l + 1;}void swap(vector<int>& nums, int i, int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
};