LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 对于一个数 n，放在数组的第 n 个位置，这样数和其所在位置对应。当所有数都这样放好后，从头开始遍历数组，找到第一个不对应的数 nums[i]，i + 1 就是结果，如果每个数都对应，结果就是最后一个数（或数组长度）加 1

1 2 0 => 1 2 0 => 0 所在位置不对应 => 返回 3
3 4 -1 1 => 1 -1 3 4 => -1 所在位置不对应 => 返回 2
7 8 9 11 12 => 7 8 9 11 12 => 7 所在位置不对应 => 返回 1
1 2 3 => 均对应，返回 4

• 解法如下

class Solution {
 public:
  int firstMissingPositive(vector<int>& nums) {
    if (empty(nums)) {
      return 1;
    }
    int sz = size(nums);
    for (int i = 0; i < sz; ++i) {
      // 防止调整到越界位置
      while (nums[i] != i + 1 && nums[i] - 1 >= 0 && nums[i] - 1 < sz) {
        if (nums[i] == nums[nums[i] - 1]) {
          break;  // 避免一直交换相等元素导致的死循环
        }
        swap(nums[i], nums[nums[i] - 1]);  // 调整元素位置直到不能调整
      }
    }
    for (int i = 0; i < sz; ++i) {
      if (nums[i] != i + 1) {
        return i + 1;
      }
    }
    return sz + 1;
  }
};