LeetCode.41 缺失的第一个整数—原地哈希算法题解难点剖析

题目链接：https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked

原题解：https://leetcode.cn/problems/first-missing-positive/solutions/7703/tong-pai-xu-python-dai-ma-by-liweiwei1419

最近在疯狂的刷算法题，刷到这一题的时候被里面的判断逻辑狠狠地拷打了，不过终于是想通了，给出我个人的解释，希望能帮到正在学习这道算法的人。下面不再介绍题目，直接给出解法：

代码展示

public class Solution {

    public int firstMissingPositive(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                // 满足在指定范围内、并且没有放在正确的位置上，才交换
                // 例如：数值 3 应该放在索引 2 的位置上
                swap(nums, nums[i] - 1, i);
            }
        }

        // [1, -1, 3, 4]
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        // 都正确则返回数组长度 + 1
        return len + 1;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

关键判断条件分析

我们着重关注 while 语句里的最后一个判断条件：

nums[nums[i] - 1] != nums[i]

先讲讲我对哈希原理的认知，以及本题的关联

在日常编程中，常见的哈希类数据结构都依赖哈希函数来确定数据的存储位置。以Java为例，通常使用 hashcode() 函数的结果对集合长度取余，最后得到的这个值，就是我们在集合中存储的位置。

而本题采用的原地哈希原理是：将数据的值减 1，所得结果即为该数据对应的存放地址。基于此原理，在遍历数组元素时，核心任务就是判断每个元素是否存放在了正确的地址上。

代码判断逻辑示例

假设在遍历数组的过程中，当前访问到的元素下标为 7，其对应的值为 6。根据上述原地哈希原理，数值 6 应该被放置在下标为 5 的位置。下面通过代码逻辑详细拆解判断过程：

当前遍历到的元素：通过 nums[7] 获取，其值为 6。
当前元素应存放位置的下标：计算方式为 nums[7] - 1，即 6 - 1 = 5。
获取应存放位置的值：使用 nums[nums[7] - 1] 来获取，也就是 nums[5] 。
判断逻辑：通过比较 nums[nums[7] - 1] 与 nums[7] 是否相等，来确认当前元素是否处于正确位置。即判断 nums[5] 的值是否等于 6。

需要再次强调，nums[7] - 1 代表 nums[7] 这个值应该存放的位置下标，而 nums[nums[7] - 1] 则是该下标位置实际存储的值。这种判断逻辑关注的是当前遍历位置的值，其对应的值是否在正确位置，而不是判断当前位置是否存放了正确的值（这也是后续要提及的错误代码逻辑）。

错误判断条件分析

很多人会用 i == nums[i] - 1 进行判断，其实单独看此判断本身没问题，包括一些测试样例都能跑通，但是仔细去看就会发现问题。

条件含义分析

i：代表当前下标。
nums[i] - 1：表示当前下标拿出的元素的值减 1 得到的值。
比如i=5,nums[i]=7。那么nums[i]-1就是6。

这意味着这段代码逻辑是在判断当前位置是否存放了正确元素，而不是当前位置的元素是否在正确的位置上。

与原代码逻辑对比

原代码是在判断当前位置的元素是否处于正确位置。也就是说，原代码的 while 循环不关注当前位置是否存储了正确元素，只在意当前位置元素所对应的位置是否已有正确的值。例如 nums[3] = 7，它会把 7 存放在 6 的位置，而不关心 nums[3] 是否等于 4。

错误场景示例

假设输入数组为 {1, 1}：

当 i = 0 时，判断无误并进行交换。
当 i = 1 时，下标 1 的位置应存放 2。代入 i != nums[i] - 1 可得 1 != 0，只有当数组中出现 2 并将其存放在下标为 1 的位置时，循环才会跳出。

所以该判断语句的缺陷在于：数组内必须包含全部小于等于数组长度的值，否则会陷入死循环。

总结

感觉这道算法题其实更像数学题一点，看题解这里的判断语句真的思考了好久好久都没理解，最后想通的时候简直是惊呼WC了。真的很考验人的数学抽象思维和逻辑能力。

LeetCode.41 缺失的第一个整数 原地哈希 个人的理解