面试题3（一）：数组中重复的数字

从值为什么能当下标开始

先预测：数组[2, 3, 1, 0, 2, 5, 3]里，为什么不需要排序或哈希表，也能在线性时间内找到重复？这道“数组中重复的数字”问题，关键不是“整数容易比较”，而是长度为n且所有数字范围在0..n-1。每个合法数字m天然对应唯一槽位numbers[m]。

原书题意只要求找出任意一个重复数字，允许修改输入。于是可以尝试让每个数字都回到“值等于下标”的位置：数字0放下标0，数字1放下标1。若数字m准备归位时发现已经等于m，两个不同位置都持有同一个值，m就是重复数字。

换成自然语言，契约是：数字范围在0到n-1，因此可以把数字m放到下标m的位置。整个过程只做原地交换，并保持O(1)额外空间。这四句话分别对应值域、状态映射、输入副作用和资源上界，不能只记最后的复杂度结论。

把查重问题改成“每个槽是否被第二次占用”。它成立依赖两个强前提：值域完整落在可访问下标内，并且调用者允许重排数组。少一个前提，都不能直接套用。

先把输入契约写完整

输入数组长度为n，每个数字必须在0..n-1。这一条要在任何numbers[numbers[i]]访问之前验证，否则负数或数字n会造成越界。作者源码先扫描完整数组检查值域，再进入交换阶段；这是安全性的一部分，不是可省略的“额外判断”。

题目允许多个数字重复，也允许同一数字重复多次，只需返回任意一个。因此测试[2,4,2,1,4]时，2和4都应是合法答案。若测试固定期望2，就把多解题错误地缩成单解题。

允许修改输入意味着调用结束后数组顺序可能与调用前不同。接口要明确这个副作用。若调用方仍需要原顺序，可以先复制再运行，代价是O(n)额外空间；或者换用哈希集合。不能一边宣称额外空间O(1)，一边在函数内部偷偷复制数组。

原地归位算法

外层从i=0扫描到n-1。在位置i上，只要numbers[i] != i，当前数字还没归位。令m = numbers[i]：

1. 若numbers[m] == m，数字m已经在目标槽，当前位置又出现m，返回m。
2. 否则交换numbers[i]和numbers[m]。交换后数字m位于下标m，至少一个数字新近归位。
3. 位置i换来另一个数字，继续while检查，直到当前位置也归位或发现重复。

#include <optional>
#include <span>
#include <utility>
 
std::optional<int> find_duplicate(std::span<int> numbers) {
    if (numbers.empty()) {
        return std::nullopt;
    }
 
    const int n = static_cast<int>(numbers.size());
    for (int value : numbers) {
        if (value < 0 || value >= n) {
            return std::nullopt;
        }
    }
 
    for (int i = 0; i < n; ++i) {
        while (numbers[i] != i) {
            const int value = numbers[i];
            if (numbers[value] == value) {
                return value;
            }
            std::swap(numbers[i], numbers[value]);
        }
    }
    return std::nullopt;
}

std::optional<int>把“找到的重复值”与“未找到或输入非法”表示成不同状态，但上面仍把两类失败合并为nullopt。生产接口可以返回结构化结果或错误枚举，区分invalid_range和not_found；面试中至少要口头说明当前返回契约。

原作者接口使用bool表示成功，并通过int* duplication输出值。若保留该签名，还应验证输出指针不为空：

bool duplicate(int numbers[], int length, int* duplication) {
    if (numbers == nullptr || duplication == nullptr || length <= 0) {
        return false;
    }
    // 先校验所有值，再执行同样的归位循环。
    return false;
}

作者源码的题目契约默认调用者传入有效输出地址；把代码升级为通用接口时，空输出指针必须纳入边界，不能在找到答案后才第一次解引用并崩溃。

用不变式证明不是“碰巧交换成功”

可以写成：所有已经归位的槽j满足numbers[j] == j；后续交换不会无故破坏这些槽。若当前值m的目标槽还不是m，交换会把m放入正确位置；若目标槽已经是m，则存在两个位置包含m。

交换时要先保存value = numbers[i]。若直接连续写：

numbers[i] = numbers[numbers[i]];
numbers[numbers[i]] = numbers[i]; // numbers[i]已经改变，目标下标也变了

第二行使用的是修改后的numbers[i]，不再指向原目标槽。std::swap(numbers[i], numbers[value])或作者源码的临时变量都能保持两个下标稳定。

不仅是直觉，也是终止度量。每次没有返回重复时，至少新增一个归位值。数组只有n个槽，因此成功交换总数至多线性级别；外层和内层看似嵌套，不会退化成O(n²)。

若整个扫描结束都没有发现目标槽冲突，每个位置都可归位。长度n、合法值也只有n种时，这意味着每个值恰好出现一次，所以不存在重复。这给出了“返回未找到”的完整性证明。

边界推演与错误版本

先看最短输入。长度1时合法值只能是0，数组[0]没有重复，外层扫描一次即可结束。长度2时，[0,0]会在i=1发现目标槽0已经是0；[1,0]经过一次交换变成[0,1]，证明“当前值不等于下标”本身不等于重复，只说明它尚未归位。

同一数字出现三次也不改变算法。第一次可以把它放入目标槽，第二次遇到目标槽冲突时立即返回；题目只要求任意重复值，无需继续统计第三次。若业务要输出重复次数，提前返回就不满足需求，应该使用频次表、排序分组或其他统计结构。

多个重复值让“扫描顺序”成为实现细节。[2,4,2,1,4]可能先发现2，也可能在不同合法交换策略下先发现4。算法正确性的可观察结果是返回值确实出现至少两次，不是输出与某一参考运行完全相同。测试可以先扫描原始副本验证返回次数，再检查返回值属于允许集合。

一个常见错误是把外层写成单次if：当前位置交换一次后就立刻递增i。换入的新数字可能仍不等于i，如果不继续处理，某些值始终没有归位，后续重复证据也可能被错过。这里必须用while，直到当前位置归位或命中目标槽。

另一个错误是试图把数组“排序到完整有序”后才判断。这个算法没有这个目标；只要目标槽已占用就应立即返回。提前停止既符合任意答案契约，也避免无意义交换。若函数返回未找到，才说明所有合法值都能无冲突归位。

输入副作用还影响故障处理。值域在预扫描阶段非法时，数组尚未改变，可以安全返回；交换阶段开始后没有其他预期失败操作，因此不会出现“改了一半才发现非法值”。先整体校验再提交原地变化，让失败行为更容易向调用者说明。

复杂度为什么是O(n)

第一遍值域校验访问n个元素。归位阶段中，外层访问每个位置；每次实际交换至少把一个值放到永久正确槽，最多进行n量级的有效交换。因此总时间是O(n)，不是因为忽略了while，而是因为能为所有内层迭代找到全局线性上界。

算法只使用下标、当前值和交换临时状态，额外空间是O(1)。输入数组本身承担了状态表作用，这正是“允许修改”换来的收益。若把所有已见值另存集合，时间仍可达平均O(n)，但额外空间变成O(n)。

排序法可把相邻相等值识别出来，比较排序通常为O(n log n)，且也会修改输入；复制后排序则增加O(n)空间。原地归位优于它们的原因不是普遍更强，而是充分利用了连续紧值域。

测试要接受多解并验证副作用

作者测试覆盖重复值在最小或最大边界、存在多个重复、没有重复、非法值域和空输入。对于多解输入，测试保存允许答案集合，只要返回值属于集合就通过。这比只验证一个预期值更符合题目契约。

#include <cassert>
#include <vector>
 
void test_duplicate() {
    std::vector<int> values{2, 3, 1, 0, 2, 5, 3};
    const auto result = find_duplicate(values);
    assert(result == 2 || result == 3);
}
 
void test_no_duplicate() {
    std::vector<int> values{2, 1, 3, 0, 4};
    assert(!find_duplicate(values).has_value());
}
 
void test_invalid_range() {
    std::vector<int> values{2, 1, 3, 5, 4};
    assert(!find_duplicate(values).has_value());
}

还应明确测试后的输入可能已改变。若接口文档承诺“发现第一个重复后停止”，数组只会部分归位；测试不应假定完整排序结果。若业务要求输入保持不变，这个函数就不满足契约，应选择题3（二）的无修改方案或复制输入。

本章练习

本章回顾

1. 数组长度n、值域0..n-1让每个数字m对应目标下标m。
2. 当前值未归位时，目标槽不是同值就交换；目标槽已有同值就找到重复。
3. 所有值必须在作下标前完成校验，负数和n都会造成越界。
4. 每次成功交换至少归位一个值，因此所有while迭代总数为O(n)。
5. 算法时间O(n)、额外空间O(1)，代价是修改输入顺序。
6. 多个重复值都可能成为答案，测试要接受合法答案集合。
7. 若输入不能修改、值域不连续或要输出全部重复值，应换用其他方案。

名词解释