数组作为哈希表的妙用：寻找缺失的第一个正数

数组作为哈希表的妙用：寻找缺失的第一个正数

大家好，我是Echo_Wish，今天我们来探讨一个经典的算法问题——“缺失的第一个正数”。听起来可能有点简单，但它实际上是一个非常有意思且富有挑战性的题目，在面试中常常会碰到。更重要的是，这个问题能够帮助我们更好地理解数组和哈希表的妙用，今天我们将通过实际的代码演示，看看如何高效解决这个问题。

问题描述

题目要求我们在一个无序整数数组中，找到缺失的第一个正整数。比如，给定数组 [1, 2, 0]，缺失的第一个正整数是 3，因为数组中没有 3，而且 1 和 2 都在其中。

这个问题有一个关键点：我们不仅要找到缺失的正数，而且还要考虑高效性，让我们能够在 O(n) 的时间复杂度下解决问题。

思考与优化

一开始，我想到了一个直接的办法——使用哈希表。具体来说，我们可以把数组中的元素都记录到哈希表里，然后从 1 开始检查每个数字是否存在哈希表中。这样一来，查找每个元素的时间复杂度是 O(1)，整体复杂度是 O(n)，效率较高。

但问题在于：直接使用哈希表占用的空间较大。我们其实可以通过数组本身来模拟哈希表，从而降低空间复杂度。接下来，我们通过一个具体的方案来分析如何操作。

解决方案：用数组模拟哈希表

由于题目要求我们找到缺失的第一个正整数，我们知道正整数的范围是从 1 开始，一直到数组的长度 n。因此，我们可以通过将数组的每个元素与数组下标一一对应来实现模拟哈希表的功能。

解决步骤

1. 过滤无效值
   由于我们只关心正整数 1 到 n，任何小于 1 或大于 n 的值都不需要关心，因此我们可以直接将它们忽略。

2. 将数组值放到正确的位置
   我们可以将每个元素放到它应该去的位置，比如数字 1 放到下标 0，数字 2 放到下标 1，依此类推。这样，当我们遍历数组时，所有值都应该出现在它们对应的下标位置。

3. 找到缺失的正整数
   遍历一遍处理过的数组，找到第一个不在正确位置的值，那么它对应的下标就是缺失的第一个正整数。

代码实现

def first_missing_positive(nums):n = len(nums)# Step 1: 将无效值转换为n+1，表示这些值不参与计算for i in range(n):if nums[i] <= 0 or nums[i] > n:nums[i] = n + 1# Step 2: 将每个数字放到它对应的位置for i in range(n):val = abs(nums[i])if 1 <= val <= n:# 放置到正确的索引位置nums[val - 1] = -abs(nums[val - 1])  # 变成负值，表示已出现# Step 3: 找到第一个未被标记的位置for i in range(n):if nums[i] > 0:return i + 1  # 返回缺失的正整数# 如果所有位置都已经有值，说明缺失的正整数是n+1return n + 1# 示例测试
nums = [1, 2, 0]
print(first_missing_positive(nums))  # 输出 3nums = [3, 4, -1, 1]
print(first_missing_positive(nums))  # 输出 2

代码解析

1. 过滤无效值
   我们通过遍历数组，将所有小于 1 或大于 n 的值替换成 n + 1，这是因为在我们的问题范围内，这些数字不可能是缺失的第一个正整数。

2. 数组重排
   在第二步中，我们将每个数 x 放到下标 x-1 的位置，通过将其变成负数来标记它已经出现在数组中。这是模拟哈希表的一种方式，借助数组的空间和下标直接存储信息。

3. 查找缺失的数字
   在最后一步，我们遍历数组，查找第一个正数，它的下标就是缺失的第一个正整数。

时间与空间复杂度分析

• 时间复杂度：O(n)，我们只需要遍历数组三次。
• 空间复杂度：O(1)，我们没有使用额外的哈希表，而是直接在原数组上进行了操作。

举个例子

让我们看一个具体的例子：

假设输入是 [3, 4, -1, 1]，按照我们的思路，第一步过滤无效值，数组变成 [3, 4, 5, 1]。然后，我们将每个值放到它该在的位置。经过第二步处理后，数组变成 [-3, -4, 5, -1]。最后，我们遍历数组，发现位置 2 没有被标记（值为 5），因此缺失的第一个正整数是 2。

总结

通过这个问题，我们不难发现，数组可以作为一种高效的哈希表，通过巧妙地利用下标来存储信息，可以大大减少空间复杂度。这种思路不仅适用于“缺失的第一个正数”问题，也能在其他类似的算法题中找到应用。希望这篇文章能够帮助你更好地理解如何在面试或实际项目中利用数组来优化算法。