我的LeetCode 41难题痴迷：深入探讨第一个缺失的正数问题

LeetCode 的“缺失的第一个正数”问题（编号 41）成为了我最近的编程迷恋。这是一个看似简单却令人着迷的难题，它占据了我的思绪，驱使我去探索它的复杂之处，并尽可能地编写出最高效的 TypeScript 解决方案。这篇文章不仅仅是为了应对编码面试（尽管这是一个不错的额外收获）。它关乎解决问题的纯粹乐趣，优化的快感，以及高效代码的优雅之美。而且，因为我有点数学迷，我们甚至会深入探讨解决方案的数学基础。

问题：披着羊皮的狼

问题给出一个未排序的整数数组。你的任务：找到最小的缺失正整数。看起来很简单？再想一想。$O(n)$ 时间和 $O(1)$ 空间复杂度的约束将这个看似简单的任务变成了一个具有挑战性的算法难题。

初始挣扎：蛮力陷阱

我最初的尝试包括排序（违反了 $O(n)$ 的时间约束）和哈希集合（超过了 $O(1)$ 的空间限制）。显然，需要一种更巧妙的方法。

灵光乍现：就地转换

关键的见解是意识到我可以使用输入数组本身作为哈希表。通过重新排列元素，我可以将数字 $x$ 放置在索引 $x - 1$ 处（如果 $1 \le x \le n$，其中 $n$ 是数组长度）。这种就地转换开启了高效解决方案的道路。

代码演变：TypeScript 编年史

以下是我的代码演变的记录，其中包含详细的解释和数学见解：

版本 1：朴素方法（带有冗余交换）

function firstMissingPositive(nums: number[]): number {
  const n = nums.length

  // 将每个数字放在正确的位置，如果它在 [1, n] 范围内
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const correctIndex = nums[i] - 1
      ;[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]] // 交换
    }
  }

  // 找到第一个缺失的正数
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // 如果所有数字都在正确的位置，则缺失的数字是 n + 1
  return n + 1
}

这个版本虽然功能正常，但存在冗余交换。最坏情况下交换次数接近 $O(n^2)$，尽管平均情况更接近 $O(n)$。

解释：

1. 重新排列数组： 每个数字 nums[i] 都被放置在其“正确”索引 (nums[i] - 1) 处，如果它在 [1, n] 范围内并且不在正确的位置。

2. 识别缺失的正数： 重新排列后，第一个索引 i 满足 nums[i] !== i + 1，这表明 i + 1 是缺失的正整数。

3. 如果需要则返回 n + 1： 如果从 1 到 n 的所有数字都在正确的位置，则缺失的数字是 n + 1。

关键点：

• **就地重新排列：**我们修改数组本身以避免使用额外的空间。
• **效率：**重新排列和最终扫描都花费 $O(n)$ 时间，确保最佳性能。

版本 2：性能提升（消除冗余交换）

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  // 尽可能将数字重新排列到正确的位置
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // 不使用临时变量进行交换
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // 识别第一个缺失的正数
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

解释：

1. 高效的重新排列：

   • while 循环仅当数字在有效范围 [1, n] 内且不在其正确位置时，才直接将其交换到正确位置 (nums[idx] - 1)。
   • if 条件确保跳过无效的或已经正确的数字，避免不必要的交换。

2. 直接索引检查：

   • 在重新排列阶段，通过检查 nums[idx] 的范围和值，避免了无效的交换和冗余操作。

3. 内存高效的交换：

   • 使用解构赋值 ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) 消除了对临时变量的需求，最大限度地减少了内存使用。

4. 最小循环：

   • 该算法仅使用两次线性遍历：
     • 一次就地重新排列数组。
     • 另一次查找第一个缺失的正数。

复杂度分析：

• 时间复杂度：
  • while 循环和 for 循环都运行在 $O(n)$，使得总时间复杂度为 $O(n)$。
• 空间复杂度：
  • 该算法就地操作，不使用任何辅助数据结构，因此空间复杂度为 $O(1)$。

为什么这段代码是最佳的：

• **性能：**简化的 while 循环确保最小化冗余操作，最大化速度。
• **内存效率：**就地交换的使用以及避免额外变量确保最低的内存占用。

版本 3：针对内存优化的版本（最小空间使用）

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  while (idx < n) {
    const correctIdx = nums[idx] - 1

    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      nums[idx] = nums[correctIdx]
      nums[correctIdx] = correctIdx + 1
    } else {
      idx++
    }
  }

  for (let idx = 0; idx < n; idx++) {
    if (nums[idx] !== idx + 1) {
      return idx + 1
    }
  }

  return nums.length + 1
}

关键内存优化：

1. 使用最少临时变量的就地更新：

   • 此代码不使用 temp 变量进行交换，而是直接使用 nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1 修改数组。
   • 这消除了对临时变量的需求，减少了恒定数量的内存开销。

2. 循环中较少的临时值：

   • 代码直接在循环中计算 correctIdx，避免在核心逻辑之外存储额外的中间变量。
   • 较少的变量赋值意味着每次迭代的内存使用量略低。

3. 单次遍历重新排列：

   • 与第一个代码在 while 循环中使用嵌套条件不同，此实现以更简化的方式完成交换或推进索引，减少了运行时堆栈深度和内存使用。
   • 循环结构（带单个增量或重新排列的 while）更直接，需要更少的辅助值。

4. 无冗余检查：

   • 对 correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] 的检查简洁明了，并防止不必要的操作暂时使用堆栈或 CPU 缓存内存。
   • 这避免了为不会对结果做出贡献的操作分配额外资源。

为什么这在内存方面有所不同：

• **减少临时存储：**通过不依赖于 temp 变量并最大限度地减少中间计算，内存占用更小。
• **简化的执行：**更少的步骤和更简单的逻辑转化为每次操作更低的内存使用量。
• **改进的缓存利用率：**算法的线性、可预测的访问模式提高了 CPU 缓存性能，间接减少了内存开销。

此解决方案专注于直接的就地更新、最少的变量使用和高效的内存访问模式，使其在内存效率方面最佳。虽然节省量是恒定的 ($O(1)$)，但对于像 LeetCode 这样的竞争平台，特别是对于大型数据集而言，它们足够显著。

版本 4：优化的杰作（就地交换，无临时变量）

function firstMissingPositive(nums: number[]): number {
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] !== i + 1) {
      if (nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]) {
        break
      }

      const temp = nums[i]
      nums[i] = nums[temp - 1]
      nums[temp - 1] = temp
    }
  }

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

  return nums.length + 1
}

最终版本通过优雅的就地交换（无需临时变量）实现了最佳性能和最少的内存使用。时间复杂度现在牢固地为 $O(n)$，空间复杂度为 $O(1)$，满足所有要求。在数学上，我们在数组中执行一种循环排列，以将元素放置在其“正确”位置。

通过添加检查 (nums[i] === nums[nums[i] - 1])，我们避免了不必要的交换。这大大提高了性能，使时间复杂度更接近所需的 $O(n)$。

实现上的关键区别：

1. 避免冗余交换：

   • 提供的代码在执行交换之前明确检查 nums[i] === nums[nums[i] - 1]。当数字已经在正确位置或存在重复项时，这避免了不必要的交换。
   • 在第一个实现中，省略了此检查，即使在不必要时也可能导致冗余交换。每次额外的交换都会增加开销，尤其是在大型数组中。

2. 直接索引比较：

   • 提供的代码使用 while (nums[i] !== i + 1) 来确保一个数字被重复交换到其正确的位置，直到它被正确放置或满足无效条件。这消除了不必要的循环迭代。
   • 第一个代码没有在循环条件内明确地将数字与其预期的索引进行比较。在数字需要最小移动的情况下，它可能会执行更多操作。

3. 优化的条件检查：

   • 通过在一个 if 块中组合条件（例如，nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]），代码避免了不必要检查或计算造成的额外开销。

为什么这在 LeetCode 中很重要：

• 运行时一致性：

  • LeetCode 的运行时测量可能对不必要的操作很敏感，例如冗余交换或额外的比较。
  • 提供的代码最大限度地减少了这些操作，导致平均运行时间更快。

• 缓存效率：

  • 更少的交换和更简单的循环逻辑导致更好的 CPU 缓存利用率。现代处理器受益于可预测和简化的访问模式，而提供的代码正是如此。

结果

以下是表格形式的摘要：

此表突出了权衡以及最终解决方案的最优性。

摘要表明最佳性能和内存的尝试确实是最佳优化的，实现了：

• **1 ms 运行时间：**在性能方面与最快的结果相匹配。
• **58.9 MB 内存使用：**略高于“最佳内存”版本，但低于其他尝试。

分析：

1. 运行时间：

   • 1 ms 运行时间表明优化后的方法消除了冗余检查和不必要的交换。
   • $O(n)$ 的一致时间复杂度确保了大型数据集的可扩展性。

2. 内存：

   • 58.9 MB具有竞争力，表明尽管执行速度快，但内存占用仍然很低。与“最佳内存”（58.5 MB）相比略微增加可能是由于解构或引擎特定优化方面的差异。

3. 权衡：

   • “最佳内存”解决方案为了更低的内存使用量而稍微牺牲了运行时间。
   • “最佳性能”解决方案更侧重于速度，但内存使用略高。

结论：

优化后的解决方案取得了良好的平衡：

• 1 ms 的运行时间与性能最佳的代码一样快。
• 58.9 MB 的内存使用量接近最佳内存结果，开销可忽略不计。

这是一个周全的选择，尤其是在性能和内存都至关重要的场景中。

数学基础：循环排列和抽屉原理

核心思想围绕循环排列的概念展开。我们的目标是创建一个循环，其中每个数字 $x$ 都放置在索引 $x - 1$ 处。while 循环有效地遍历这些循环，确保每个元素都找到其指定的位置。

抽屉原理在这里起着微妙的作用。由于我们有 $n$ 个可能的位置（索引 $0$ 到 $n-1$），并且我们正在寻找范围 $[1, n+1]$ 内的缺失正整数，如果从 1 到 $n$ 的所有数字都存在，则缺失的数字必须是 $n + 1$。

迷恋仍在继续……

我对 LeetCode 41 的迷恋依然存在。我一直在寻求进一步的优化和更深入的见解。加入我的探索吧！分享你的想法、你自己的解决方案，让我们一起探索数学和算法的优雅交汇点。