[C算法]004-寻找未出现的最小整数

均采用C语言来编写，版本为C17，使用其他版本也可以，仅仅停留在算法层面，各大版本几乎区别不大

题目

2018年真题

给出一个含 $n$ 个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。

例如:
数组 $\{-5,3,2,3\}$ 未出现的最小正整数是1
数组 $\{1,2,3\}$ 未出现的最小整数是4

代码展示

这里我们就要使用原地 Hash
将所有的数放到索引为数值-1 的地方

void swap(int *a, int *b) {
    const int temp = *a;
    *a = *b;
    *b = temp;
}

int find_missing_smallest_number(int nums[], int size) {
    for (int i = 0; i < size; ++i) {
        while (nums[i] != i + 1 && nums[i] > 0 && nums[i] <= size) {
            if (nums[i] == nums[nums[i] - 1]) {
                printf("交换双方都是 %d ", nums[i]);
                break;
            }
            swap(&nums[i], &nums[nums[i] - 1]);
        }
    }

    for (int i = 0; i < size; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    return size + 1;
}

int main() {
    int a[] = {-5, 3, 2, 3, 1, 6, 8};
    const int size = sizeof(a) / sizeof(a[0]);
    const int result = find_missing_smallest_number(a, size);
    printf("%d", result);
}

代码解释

这种算法通常被称为 “原地哈希”（In-place Hashing），也被形象地称为 “萝卜坑置换法”。

它的核心思想是：利用数组下标作为哈希表的索引，将每个数字放到它“应该”在的位置上。

以下是对该算法的详细拆解：

1. 核心逻辑：萝卜坑理论

对于一个长度为 $n$ 的数组，如果我们想找缺失的最小正整数，理想情况下，数字 $1$ 应该放在下标 $0$ 的位置，数字 $2$ 应该放在下标 $1$ 的位置……以此类推，数字 $i$ 应该放在下标 $i-1$ 的位置。

规则：数值为 $\displaystyle x$ 的元素，其“正确位置”应该是 $\displaystyle \text{nums}[x-1]$ 。
操作：遍历数组，如果发现某个位置上的数字不对，就通过交换把它送到它该去的地方。

2. 代码逻辑逐行解析

A. 交换过程（While 循环）

while (nums[i] != i + 1 && nums[i] > 0 && nums[i] <= size) {
    if (nums[i] == nums[nums[i] - 1]) {
        // 防止死循环：如果目标位置已经是正确的数字了，就不要再换了
        break; 
    }
    swap(&nums[i], &nums[nums[i] - 1]);
}

nums[i] != i + 1：当前位置 $i$ 上的数字不是它应有的数字（比如下标 $0$ 存的不是 $1$ ）。
范围检查：只有当数字在 $\displaystyle [1, size]$ 之间时，我们才能在数组里找到它的“坑”。负数或大于数组长度的数无法归位，直接跳过。
去重处理：nums[i] == nums[nums[i] - 1] 是为了处理重复数字。如果当前数字 $\displaystyle x$ 想要交换到的目标位置已经坐着一个 $\displaystyle x$ 了，就停止交换，否则会陷入死循环。

B. 结果查找

for (int i = 0; i < size; ++i) {
    if (nums[i] != i + 1) {
        return i + 1;
    }
}

当所有能归位的数字都归位后，再次遍历数组。第一个满足 $\displaystyle \text{nums}[i] \neq i + 1$ 的位置，说明这里缺了数字 $\displaystyle i+1$ 。

3. 示例走读

假设输入数组为：{-5, 3, 2, 3, 1, 6, 8}，长度为 $7$ 。

i = 0: nums[0] = -5。不在 $\displaystyle [1, 7]$ 范围，跳过。
i = 1: nums[1] = 3。
- $3$ 应该去下标 $2$ 。交换 nums[1] 和 nums[2]。
- 数组变为：{-5, 2, 3, 3, 1, 6, 8}。
- 此时 nums[1] = 2，还没对。 $2$ 应该去下标 $1$ 。交换 nums[1] 和 nums[1]（自己换自己）。
- 数组不变，while 结束。
i = 2: nums[2] = 3。已经在正确位置（下标 $2$ 存 $3$ ），跳过。
i = 3: nums[3] = 3。
- $3$ 应该去下标 $2$ 。但 nums[2] 已经是 $3$ 了。
- 触发 if (nums[i] == nums[nums[i] - 1])，打印“交换双方都是 3”，break。
i = 4: nums[4] = 1。
- $1$ 应该去下标 $0$ 。交换 nums[4] 和 nums[0]。
- 数组变为：{1, 2, 3, 3, -5, 6, 8}。
- 此时 nums[4] = -5，跳过。
后续…：数字 $6$ 会归位到下标 $5$ ，数字 $8$ 超出范围。

最后检查数组：{1, 2, 3, 3, -5, 6, 8}

下标 0 是 1 (OK)
下标 1 是 2 (OK)
下标 2 是 3 (OK)
下标 3 是 3 (应该是 4，不匹配！) -> 返回 4。

4. 复杂度分析

时间复杂度： $\displaystyle O(n)$ 。
虽然代码中有嵌套的 while 循环，但每一次成功的交换都会把一个数字送到它的最终位置。数组中只有 $n$ 个数字，所以总的交换次数最多为 $n$ 次。
空间复杂度： $\displaystyle O(1)$ 。
直接在原数组上操作，不需要额外的哈希表空间，这是该算法最大的优势。

总结

这种算法本质上是将数组本身当成了哈希表。它利用了“数值范围与数组下标范围重合”这一特性，通过多次交换实现 $O(1)$ 空间的快速定位。