每日一题-4th

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

Leetcode 41. 缺失的第一个正数

题干

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例

示例 1：

1 2	输入：nums = [1,2,0] 输出：3

示例 2：

1 2	输入：nums = [3,4,-1,1] 输出：2

示例 3：

1 2	输入：nums = [7,8,9,11,12] 输出：1

思路

最自然的思路（遍历法）：按序记录数组中出现的所有正整数，最后遍历记录找到最小的没有取到的正整数（O(n)时间，O(n)空间），显然不满足题目所要求的空间复杂度；

为了满足O(1)空间，不能额外创建空间，考虑在原数组上修改。原数组如何按序记录出现的正整数，且不能排序？
因为可以在原数组上修改，所以可以考虑类似哈希的方法：将数字放在对应下标的位置，最后从后向前遍历找到最前面的元素即可；

⚠ 问题1：存在负整数。这里题目只要求正整数，所以直接抛弃（不管）数组中的负数元素；

⚠ 问题2：元素值超过数字下标（哈希经典问题）：由于不要求全部存储，所以将超过最大索引的元素也抛弃，毕竟只要找最小正整数；

思考这里的处理恰到好处：即便舍弃超过最大索引的元素，也能保证最小正整数在数组内能找到；

因为如果数组内的所有正整数都大于数组索引的话，说明1肯定不在其中（length ≥ 1），那么答案就是1；

实现

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int len = nums.size();
        for (int i = 0; i < len;) {
            // 满足：不大于索引的正整数，且需要改变位置
            if (nums[i] > 0 && nums[i] <= len && i + 1 != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
            else ++i;
        }
        for (int i = 0; i < len; ++i) {
            if (nums[i] != i + 1) return i + 1;
        }
        // 恰好数组中所有位置都对应上了，没有空缺
        return len;
    }
};