41. 缺失的第一个正数

41. 缺失的第一个正数 - 力扣（LeetCode）

class Solution {
public:
  int firstMissingPositive(vector<int>& nums) {
    int Size = nums.size();

    for (auto &x : nums)
      if (x <= 0)
        x = Size + 1;

    for (int i = 0; i < Size; ++i) {
      int I = abs(nums[i]);
      if (I < Size + 1)
        nums[I - 1] = -abs(nums[I - 1]);
    }

    int Missing;
    for (Missing = 0; Missing < Size; ++Missing)
      if (nums[Missing] > 0)
        break;

    return Missing + 1;
  }
};

题解感觉略微有些淡淡的 hack 感……硬要说修改原数组确实也叫 $\mathrm O(1)$ 吧，这点在复杂度卡得很死的情况下应该有用。

这里尤其要注意的是利用负数打标记会导致两个问题：一是有可能访问到先前已经被取负的元素，所以 I 才需要进行 abs() 处理；二是必须要保证打完的标记一直存在，也即一直是负数，所以对 nums[I - 1] 的赋值也需要进行 abs()。

二刷的时候写一下置换方法。

二刷

class Solution {
public:
  int firstMissingPositive(vector<int>& nums) {
    // Set all non-positive numbers to Size + 1, in order to avoid messing with
    // real positive values after marking.
    int Size = nums.size();
    for (int &X : nums) {
      if (X <= 0)
        X = Size + 1;
    }

    // Mark all positive indices.
    for (int i = 0; i < Size; ++i) {
      int IdxP1 = std::abs(nums[i]);
      // Since we already make all non-positive numbers positive, there's no
      // need to check for non-positive cases.
      // if (IdxP1 < 1 || IdxP1 > Size())
      if (IdxP1 > Size)
        continue;
      nums[IdxP1 - 1] = -std::abs(nums[IdxP1 - 1]);
    }

    // Find the first index that's positive (not marked).
    int Missing = 1;
    for (int X : nums) {
      if (X >= 0)
        break;
      else
        ++Missing;
    }
    return Missing;
  }
};

基本上跟官解是一样的，三次遍历，先把负数全部变成 Size + 1 避免冲突，然后打标记时注意恒负，最后找第一个未标记的数。

「打标记」的技巧其实有个名字叫「原地哈希」。对于本题，哈希函数是

$$ f(\mathrm{nums}[i])=\mathrm{nums}[i]-1 $$

至于置换方法，也是采用这个哈希函数的思路。主要需要注意的是交换两个相同的数可能会导致的死循环的问题。

class Solution {
public:
  int firstMissingPositive(vector<int>& nums) {
    int N = nums.size();
    for (int i = 0; i < N; ++i) {
      // Utilize short-circuit to determine range before confirming position.
      // We also need to check for identical swaps e.g. [1, 1].
      // Note that the nums[i] != i + 1 is not mandatory, since swap(x, x) is
      // identity operation.
      while (nums[i] > 0 && nums[i] <= N && nums[i] != i + 1 &&
             nums[nums[i] - 1] != nums[i])
        std::swap(nums[nums[i] - 1], nums[i]);
    }

    for (int i = 0; i < N; ++i) {
      // If not at the correct position, return.
      if (nums[i] != i + 1)
        return i + 1;
    }
    return N + 1;
  }
};