力扣 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);}
};