如何从多个动态数组中找出缺失的整数？附C++代码补全求助

针对你提出的问题——从完整数组中找出另一个数组缺失的整数，这里有几种实用且高效的解法，同时我会帮你完善现有的C++代码。

1. 求和法（简单高效） #

这个方法的核心逻辑是：计算完整数组的总和，减去缺失元素的数组的总和，差值就是缺失的整数。

优点 #

• 时间复杂度O(n)，只需要遍历两个数组各一次
• 空间复杂度O(1)，不需要额外存储空间（除了变量）

示例逻辑 #

比如你的示例中，array_1的总和是0+1+2+...+9=45，array_2的总和是0+3+4+6+7+2+9+8+5=44，45-44=1，就是缺失的数。

2. 异或法（避免溢出问题） #

如果数组中的整数范围很大，求和可能会导致整数溢出，这时候异或法是更好的选择。

核心逻辑 #

• 相同的整数异或结果为0
• 0和任意整数异或结果为该整数本身
• 把完整数组和缺失数组的所有元素依次异或，最终结果就是缺失的整数（因为其他数都出现两次，异或后抵消，只剩缺失的数）

示例逻辑 #

完整数组异或结果：0^1^2^...^9，再异或array_2的所有元素，最终结果就是1。

3. 哈希集合法（通用场景） #

如果数组中的元素不是连续整数，或者范围非常大，哈希集合法更通用。

核心逻辑 #

• 把缺失元素的数组所有元素存入哈希集合
• 遍历完整数组，找到第一个不在集合中的元素，就是缺失的数

优点 #

• 不依赖元素的连续性，适用于任意整数数组
• 查找操作是O(1)，整体时间复杂度O(n)

完善你的C++代码 #

我基于求和法修改了你的代码，补全了缺失的输出逻辑，同时优化了代码的可读性：

#include <iostream>
#include <array>
using namespace std;

int main() {
    int test_case_count;
    array<int, 9> incomplete_array;
    array<int, 10> complete_array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // 预先计算完整数组的总和
    int complete_sum = 0;
    for (int num : complete_array) {
        complete_sum += num;
    }
    
    cout << "请输入测试用例数量：";
    cin >> test_case_count;
    
    for (int case_idx = 0; case_idx < test_case_count; case_idx++){
        int incomplete_sum = 0;
        cout << "请输入第" << case_idx + 1 << "组9个整数：" << endl;
        for (int i = 0; i < 9; i++){
            cin >> incomplete_array[i];
            incomplete_sum += incomplete_array[i];
        }
        // 计算缺失的数并输出
        int missing_num = complete_sum - incomplete_sum;
        cout << "第" << case_idx + 1 << "组测试用例中缺失的数是：" << missing_num << "\n\n";
    }
    return 0;
}

代码说明 #

1. 先计算complete_array的总和，避免每次测试用例都重复计算
2. 支持多组测试用例输入，符合你代码中n的设计逻辑
3. 增加了提示性输入文本，让用户更清楚操作流程
4. 最终输出每组测试用例对应的缺失整数

如果你想改用异或法，只需要把求和部分替换成异或逻辑即可：

// 预先计算完整数组的异或结果
int complete_xor = 0;
for (int num : complete_array) {
    complete_xor ^= num;
}

// 每组测试用例的异或计算
int current_xor = complete_xor;
for (int i = 0; i < 9; i++){
    cin >> incomplete_array[i];
    current_xor ^= incomplete_array[i];
}
int missing_num = current_xor;

内容的提问来源于stack exchange，提问作者Neil John Jomaya