缺失的第一个正数-面试热题 100？-Lua 中文代码解题第5题

缺失的第一个正数-面试热题 100？-Lua 中文代码解题第5题

解题思路： 

1. 遍历数组并尝试将元素放入正确的位置： 遍历输入数组 nums，对于每个元素 nums[i]：

   • 如果 nums[i] 是一个正整数，并且它的值小于或等于数组的长度（即在有效范围内），则检查对应下标的值 nums[nums[i]] 是否与 nums[i] 相等。
     • 如果不相等，说明 nums[i] 的位置不是其应该在的位置。此时交换 nums[i] 和 nums[nums[i]] 的值，试图将 nums[i] 放到它应该在的位置上（nums[nums[i]] 应该为 i）。

2. 寻找未出现的最小正整数： 再次遍历数组 nums，由于前面的操作，数组中下标 i 与值 nums[i] 不匹配的位置（nums[i] 不等于 i）表示原数组中数值为 i 的元素没有出现过。因此，我们只需找到第一个这样的位置 i，返回 i 作为结果。

通过这个方法，可以在遍历一次数组的基础上完成题目要求的任务，虽然在极端情况下时间复杂度可能退化，但在大多数情况下可以实现 O(n) 的平均时间复杂度，并且只使用了常数级别的额外空间。

中文代码 -- 无注释版

函数 缺少的首个正数(输入数组)
    局部 n = #输入数组
    因为 i = 1, n 做
        当 输入数组[i] > 0 与 输入数组[i] <= n 与 输入数组[输入数组[i]] ~= 输入数组[i] 做
            局部 临时数 = 输入数组[i]
            输入数组[i] = 输入数组[临时数]
            输入数组[临时数] = 临时数
        结束
    结束

    因为 i = 1, n 做
        如果 输入数组[i] ~= i 即
            返回 i
        结束
    结束
    返回 n + 1
结束

中文代码 -- 带注释的如下：

-- 缺少的首个正数函数
-- 参数：输入数组，一个包含任意整数的数组
-- 返回值：一个整数，表示输入数组中缺失的首个正数
函数 缺少的首个正数(输入数组)
    局部 n = #输入数组  -- 输入数组的长度

    -- 将输入数组中每个元素替换为该元素所指向的索引上对应的值（如果该值是有效的）
    因为 i = 1, n 做
        当 输入数组[i] > 0 与 输入数组[i] <= n 与 输入数组[输入数组[i]] ~= 输入数组[i] 做
            局部 临时数 = 输入数组[i]
            输入数组[i] = 输入数组[临时数]
            输入数组[临时数] = 临时数
        结束
    结束

    -- 查找缺失的首个正数
    -- 如果输入数组中的元素不等于其对应的索引值，则返回该索引
    因为 i = 1, n 做
        如果 输入数组[i] ~= i 即
            返回 i
        结束
    结束
    -- 如果没有找到缺失的正数，则返回数组长度加一
    返回 n + 1
结束

这段代码运行后将会输出：

-- 测试用例
局部 输入数组1 = {1, 2, 0}
输出(缺少的首个正数(输入数组1))  -- 输出：3

局部 输入数组2 = {3, 4, -1, 1}
输出(缺少的首个正数(输入数组2))  -- 输出：2

局部 输入数组3 = {7, 8, 9, 11, 12}
输出(缺少的首个正数(输入数组3))  -- 输出：1