深入解析：如何在数组中高效找出重复和缺失的数字

在这篇文章中，我们将深入探讨一个在编程面试和实际开发中都非常经典的问题：如何在一个包含 1 到 n 范围内数字的数组中，快速找出那个“多出来”的重复数字和“丢失”的缺失数字。这不仅是一个算法挑战，更是锻炼我们逻辑思维和代码优化能力的绝佳机会。我们将一起探索从最直观的解法到利用数学和位运算的高级技巧，并分析它们各自的适用场景。

问题描述与背景

首先，让我们明确一下我们要解决的问题。假设我们有一个大小为 INLINECODE1d849653 的数组 INLINECODEa73ec627，这个数组本应包含从 INLINECODEe96aefe2 到 INLINECODE081073d7 的每一个整数，且每个整数只出现一次。然而，由于数据错误或系统异常，数组现在的状态变得“不完美”了：在这个范围内，有一个数字被意外地复制了一份（导致重复），而另一个数字则彻底消失了（导致缺失）。

我们的任务就是编写一个高效的算法，从这堆看似混乱的数据中，精准地把这两个“捣乱分子”找出来。

#### 示例演示

为了让你更直观地理解，让我们看一个简单的例子：

> 输入：arr[] = [3, 1, 3]

> 输出：[3, 2]

> 解释：数字 3 出现了两次（它是重复数字），而数字 2 不见踪影（它是缺失数字）。

再来看一个稍微复杂一点的例子：

> 输入：arr[] = [4, 3, 6, 2, 1, 1]

> 输出：[1, 5]

> 解释：这里数字 1 出现了两次，而本该出现的数字 5 却缺失了。

核心解法探索

我们将从最简单的方法开始，逐步深入到更优化的解决方案。你会发现，随着我们对问题本质理解的加深，算法的空间复杂度和时间复杂度都会得到显著的改善。

#### 方法 1：使用辅助频率数组

这是最直观、最容易想到的方法。既然我们想知道每个数字出现的次数，为什么不直接开一个“计数器”数组来记录它们呢？

基本思路：

• 创建一个大小为 INLINECODE4c892620 的辅助数组 INLINECODE9dcb2145，初始化为 0。
• 遍历原数组，对于每个数字 INLINECODE2d69bae7，将 INLINECODE9748e561 加 1。
• 再次遍历 INLINECODE8353e3d2 数组，检查下标 INLINECODEed02f7ec 到 n：

– 如果 INLINECODEa6292b43，说明 INLINECODE9baf29d3 是重复数字。

– 如果 INLINECODEa83bc2e1，说明 INLINECODE785b56b9 是缺失数字。

代码实现与解析：

让我们来看看如何在 C++ 中实现这一逻辑。

#include 
#include 
using namespace std;

// 定义寻找重复和缺失元素的函数
vector findTwoElement(vector& arr) {
    int n = arr.size();
    
    // 创建频率数组，大小为 n+1 (下标 0 不使用)
    // 初始化所有计数为 0
    vector freq(n + 1, 0);
    int repeating = -1, missing = -1;
    
    // 第一次遍历：统计每个数字出现的频率
    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
    }
    
    // 第二次遍历：根据频率判断结果
    for (int i = 1; i <= n; i++) {
        if (freq[i] == 0) 
            missing = i;      // 频率为 0，说明该数字缺失
        else if (freq[i] == 2) 
            repeating = i;    // 频率为 2，说明该数字重复
    }
    
    // 返回结果：{重复数字, 缺失数字}
    return {repeating, missing};
}

int main() {
    vector arr = {3, 1, 3};
    vector ans = findTwoElement(arr);
    // 输出结果
    cout << "重复数字: " << ans[0] << ", 缺失数字: " << ans[1] << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：O(n)。我们遍历了数组两次（一次统计，一次查找），虽然常数是 2，但在大 O 表示法中仍是线性的。
• 空间复杂度：O(n)。这是这种方法的主要缺点，因为我们引入了一个额外的数组来存储频率信息。如果 n 非常大（比如 10 亿），这种空间消耗是不可接受的。

#### 方法 2：原地标记法（修改原数组）

既然引入额外数组这么浪费空间，我们能不能利用题目中给出的“数字范围在 1 到 n 之间”这个条件，直接在原数组上做标记呢？答案是肯定的。

基本思路：

数组中的数字 INLINECODEe796ed88 刚好可以作为数组的索引。我们可以利用 INLINECODE449ae9d3 的正负号来记录 val 是否已经出现过。

• 遍历数组，对于每个元素 INLINECODEf6a150af，计算其对应的索引 INLINECODE2c08b795（注意处理负数和索引偏移）。
• 检查该索引位置的值：

– 如果是正数，将其变为负数（标记为“已见过”）。

– 如果已经是负数，说明 abs(arr[i]) 之前出现过，这就是我们的重复数字。

• 最后再遍历一次数组，找到那个索引位置 INLINECODEb054d21e 仍然是正数的位置，则 INLINECODE93f4fb28 就是缺失数字（因为它对应的索引从未被访问过，所以没被打上负号）。

> 注意： 这种方法会修改原数组的内容。如果在实际开发中不能修改原数组，你需要先复制一份。

#include 
#include 
#include  // 用于 abs 函数
using namespace std;

vector findTwoElement(vector& arr) {
    int n = arr.size();
    int repeating = -1, missing = -1;
    
    for (int i = 0; i < n; i++) {
        // 获取当前元素对应的绝对值索引
        // 比如元素 3 对应索引 2
        int val = abs(arr[i]);
        int index = val - 1;
        
        if (arr[index] < 0) {
            // 如果已经是负数，说明之前标记过，该数字是重复的
            repeating = val;
        } else {
            // 第一次遇到，将其标记为负数
            arr[index] = -arr[index];
        }
    }
    
    // 恢复数组状态并查找缺失数字
    // 这一步也可以分开做，为了清晰展示逻辑，这里再次遍历查找正数
    for (int i = 0; i  0) {
            // 索引 i 的位置是正数，说明数字 i+1 从未出现
            missing = i + 1;
        }
    }
    
    return {repeating, missing};
}

int main() {
    vector arr = {4, 3, 6, 2, 1, 1};
    vector ans = findTwoElement(arr);
    cout << "重复数字: " << ans[0] << ", 缺失数字: " << ans[1] << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：O(n)。仍然是线性遍历。
• 空间复杂度：O(1)。我们没有使用额外的数组空间，只使用了几个变量。这是一个巨大的优化！

#### 方法 3：数学方程法

作为程序员，有时候用数学思维思考能带来意想不到的简化。让我们建立方程组来解这个问题。

设 INLINECODE35010d74 为 1 到 n 的自然数之和，INLINECODE778e3f86 为平方和。

设 INLINECODEc3690422 中的元素之和为 INLINECODEc7e36d29，平方和为 S2‘。

设重复数字为 INLINECODE1745f5b5，缺失数字为 INLINECODEe971ee1f。

根据题意，我们可以得到两个等式：

• 和的差值：(S - S‘) = Y - X （因为数组里多加了一个 X，少加了一个 Y）
• 平方和的差值：(S2 - S2‘) = Y^2 - X^2

我们知道 INLINECODE65138257 可以因式分解为 INLINECODEfd221884。

结合第一个等式，我们可以求出 Y + X。

有了 INLINECODE68d2456e 和 INLINECODEa6500f3f，我们就能轻松解出 INLINECODE5c531656 和 INLINECODE72022e56 了！

#include 
#include 
#include 
using namespace std;

vector findTwoElement(vector& arr) {
    long long n = arr.size();
    
    // 计算自然数的和 与 平方和
    long long S = n * (n + 1) / 2;
    long long S2 = n * (n + 1) * (2 * n + 1) / 6;
    
    long long arrSum = 0, arrSquareSum = 0;
    for (int num : arr) {
        arrSum += num;
        arrSquareSum += (long long)num * num;
    }
    
    // diff = Y - X
    long long diff = S - arrSum;
    // diff2 = Y^2 - X^2 = (Y - X)(Y + X)
    long long diff2 = S2 - arrSquareSum;
    
    // sum = Y + X
    long long sum = diff2 / diff;
    
    // 解方程组：
    // Y - X = diff
    // Y + X = sum
    // 相加得 2Y = sum + diff => Y = (sum + diff) / 2
    // 相减得 2X = sum - diff => X = (sum - diff) / 2
    
    long long missing = (sum + diff) / 2;
    long long repeating = (sum - diff) / 2;
    
    return {(int)repeating, (int)missing};
}

注意事项：

这种方法在数学上很优雅，但要注意溢出问题。如果 INLINECODE9c3568cd 很大，INLINECODE13507b80 会非常大，计算平方和时很容易超过 INLINECODE9da348e5 的范围，必须使用 INLINECODE112bc21f 类型。

#### 方法 4：异或（XOR）运算法

这是最位元化的解决方案，空间复杂度是 O(1)，且不会发生溢出。它利用了异或运算的几个特性：

• x ^ x = 0
• x ^ 0 = x
• 异或运算满足交换律和结合律。

基本思路：

• 让我们将数组中所有元素与 INLINECODE980d3270 到 INLINECODE2a41d810 的所有数字进行异或。

* 设重复数字为 INLINECODEed8331a9，缺失数字为 INLINECODE477cf146。

* 对于数组中出现的所有其他数字，它们都在 INLINECODE482ebb23 到 INLINECODE3c4b009d 中出现过，异或后会互相抵消（变成 0）。

* 剩下的结果将是 INLINECODE33998214（因为 INLINECODEa8d9c1a6 在数组里多出现了一次，INLINECODE9e3cdb5e 在 INLINECODE6086eba7 里多出现了一次）。

• 现在我们有了 INLINECODE7749118a。因为 INLINECODE9d05e9f4，所以 INLINECODE8a7db211 一定不为 0，这意味着 INLINECODE93ae0b51 的二进制表示中至少有一位是 INLINECODE0e030f1c。我们找到任意一个为 INLINECODE6a20a7bb 的位（比如最右边的 1）。
• 根据这个位是 INLINECODE89a111a7 还是 INLINECODE20172e8e，我们可以将所有数字（数组元素和 1..n）分成两组。

* 一组是该位为 1 的数字。

* 另一组是该位为 0 的数字。

• 分别对这两组进行异或。

* 在其中一组里，所有的普通数字都会抵消，剩下的要么是 INLINECODE37288a7b，要么是 INLINECODE07437034。假设我们找到了 X。

• 最后，遍历原数组，确认 INLINECODE25c1fe6b 是否真的在数组中出现两次。如果是，则 INLINECODE4805df54 是重复数字，另一个是 Y；否则，反之（虽然逻辑上我们分组时已经区分了，但这一步是为了确定哪个是重复、哪个是缺失）。

#include 
#include 
using namespace std;

vector findTwoElement(vector& arr) {
    int n = arr.size();
    
    // 第一步：计算 XOR
    int xorRes = 0;
    for (int i = 0; i < n; i++) {
        xorRes ^= arr[i];
        xorRes ^= (i + 1);
    }
    // 现在 xorRes = X ^ Y
    
    // 第二步：找出 xorRes 中最右边的置位（Set Bit）
    // 这将用于区分 X 和 Y
    int setBit = xorRes & ~(xorRes - 1);
    
    int bucket1 = 0, bucket2 = 0;
    
    // 第三步：根据 setBit 将数字分为两组
    for (int i = 0; i < n; i++) {
        if (arr[i] & setBit) 
            bucket1 ^= arr[i];
        else 
            bucket2 ^= arr[i];
            
        if ((i + 1) & setBit) 
            bucket1 ^= (i + 1);
        else 
            bucket2 ^= (i + 1);
    }
    
    // 此时 bucket1 和 bucket2 分别就是 X 和 Y
    // 但我们需要分清哪个是重复，哪个是缺失
    int repeating = -1, missing = -1;
    
    // 检查 bucket1 是否在数组中出现过两次（简单检查：遍历数组看是否有等于 bucket1 的）
    for (int num : arr) {
        if (num == bucket1) {
            repeating = bucket1;
            missing = bucket2;
            break;
        } else if (num == bucket2) {
            repeating = bucket2;
            missing = bucket1;
            break;
        }
    }
    
    return {repeating, missing};
}

常见错误与解决方案

在解决这个问题时，你可能会遇到一些坑。让我们看看如何避开它们：

• 忽略索引偏移：在很多编程语言中，数组是从 0 开始索引的，而我们的题目是从 1 开始计数。在方法 2（原地标记法）中，计算索引时一定要记得 index = abs(arr[i]) - 1，否则会导致数组越界或逻辑错误。
• 整数溢出：在方法 3（数学法）中，计算平方和时非常容易溢出。如果你的 INLINECODE71388cd0 达到 INLINECODE42a984aa 级别，普通的 32 位整数根本存不下。务必使用 INLINECODEf6269bb3 或 INLINECODE79f941e0。
• 数组不可修改的限制：虽然原地标记法空间复杂度很低，但如果题目明确要求不能修改输入数组，你就必须回退到方法 1 或使用方法 3/4。

性能优化与最佳实践

• 面试首选：如果你在面试中遇到这道题，

* 如果不限制空间复杂度，方法 1（频率数组）是最稳妥的，不容易写错，代码清晰。

* 如果要求 O(1) 空间且可以修改数组，方法 2（原地标记）是最巧妙的。

* 如果要求 O(1) 空间且不能修改数组，方法 4（异或）是最佳选择，虽然代码逻辑最绕。

• 边界条件：永远别忘了检查 n 为 1 或 2 的情况，或者数组已经是有序的情况。良好的代码应当能够处理各种极端输入。

总结

在这篇文章中，我们通过四种不同的视角剖析了“查找重复和缺失数字”这个问题。从直观的空间换时间，到精妙的位运算，每种方法都有其独特的价值和适用场景。希望这次深入的探索不仅让你学会了这道题的解法，更重要的是提升了你分析问题、优化代码的思维能力。下次遇到类似的数据结构问题时，试着像这样多角度思考，你会发现编程的世界充满了逻辑之美！