力扣 41. 缺失的第一个正数

🔗 https://leetcode.cn/problems/first-missing-positive

题目

• 给定一个数组，有正数有负数，未排序，返回没有出现的最小的正数
• 要求时间复杂度o(n)，使用常数级别额外空间

思路

• solution 1
  • 用 set 保存所有大于零的数，从 1 开始遍历，直到找不到，便是缺失的第一个正数
  • 时间复杂度满足要求，空间复杂度超标，不能代码可以 AC
• solution 2
  • 用了一个很巧妙的空间复用，利用当前的 nums 数组，使得 nums[index] 对应数字 index + 1，这样从 0 开始遍历，找到的第一个 index + 1 ≠ nums[index] 的，就是缺失的第一个正数，如果都有，那缺失的第一个正数就是 nums.size() + 1
  • 设置数组 index + 1 = nums[index] 的方式，就是判断当前的元素是否是 1-N 之间，若在则把这个数字通过交换放在对应的位置上

代码

class Solution {
public:
    int solution1(vector<int>& nums) {
        unordered_set<int> s;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) s.insert(nums[i]);
        }
        int ans = 1;
        while (s.find(ans) != s.end()) ans++;
        return ans;
    }
    int solution2(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            while (nums[i] > 0 && nums[i] <= n && i != (nums[i]-1)) {
                int curr_num = nums[i];
                if (curr_num == nums[curr_num -1]) break;
                nums[i] = nums[curr_num-1];
                nums[curr_num-1] = curr_num;  
            }
        }
        for (int i = 0; i < n ; i++) {
            if (nums[i] != (i+1)) return i+1;
        }
        return n+1;
    }

    int firstMissingPositive(vector<int>& nums) {
        //return solution1(nums);
        return solution2(nums);
        
    }
};