原地哈希

原地哈希的前提是什么？

• 前提: 数组长度为 n, 且元素取值被限制在 [1, n] 附近;
• 思想: 把数组本身当作哈希表, 下标 i 期望存放值为 i + 1;
• 收益: 省掉额外的哈希表空间, 空间复杂度降为 O(1);

如何找出缺失的第一个正数？

• 归位: 反复把值 v ∈ [1, n] 交换到下标 v - 1;
• 防死循环: 交换后若 nums[cur] 仍等于 v, 说明目标位置已有相同值, 手动推进 cur;
• 查找: 第一个满足 nums[i] !== i + 1 的位置, 答案就是 i + 1;
• 兜底: 所有位置都归位正确时, 答案是 n + 1;
• 复杂度: 时间 O(n), 空间 O(1);

function firstMissingPositive(nums: number[]): number {
  let cur = 0;
  while (cur < nums.length) {
    const num = nums[cur];
    if (num < 1 || num > nums.length) {
      cur++;
      continue;
    }
    [nums[cur], nums[num - 1]] = [nums[num - 1], nums[cur]];
    // 目标位置原本就是同一个值, 交换无效, 换下一个
    if (nums[cur] === num) cur++;
  }

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  return nums.length + 1;
}

如何用"取负标记"找出所有重复元素？

• 家: 下标 num - 1 是值 num 对应的位置;
• 标记: 第一次访问到 num 时, 把 nums[num - 1] 取负;
• 命中: 再次访问到 num 时该位置已经是负数, 说明重复;
• 还原: 取绝对值即可恢复原值, 因此不影响后续访问;
• 复杂度: 时间 O(n), 空间 O(1);

function findDuplicates(nums: number[]): number[] {
  const result: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    const num = Math.abs(nums[i]);
    const target = num - 1;
    if (nums[target] > 0) nums[target] = -nums[target];
    else result.push(num);
  }
  return result;
}