查找数组缺失数字的C++代码第10个测试用例失败原因求解

问题背景 #

给定1,2,…,n中除一个整数外的所有正整数，找出缺失的整数。
输入规则：

• 第一行输入整数n（2≤n≤2×10^5）
• 第二行输入n−1个1到n范围内的互不重复的整数
  输出要求：打印缺失的整数。

原实现代码 #

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::endl;
using std::sort;
int main()
{
    int x = 0;
    int n;                                  // Enter Size of 2 array
    cin >> n;                               // enter 5
    long long *ptr1 = new long long[n - 1]; // size of array must be less than 5 by one n-1
    for (int x = 0; x < n - 1; x++)
    {
        cin >> ptr1[x];
    }
    sort(ptr1, ptr1 + (n - 1));
    for (int z = 1; z < n; z++)
    {
        if (z != ptr1[x])
        {
            cout << z;
            break;
        }
        x++;
    }
    return 0;
}

代码存在的问题 #

1. 未处理缺失值为n的边界情况 #

你设置的第二层循环条件为z < n，z最大只会遍历到n-1，如果1到n-1的所有数都存在，缺失的刚好是最大值n，代码会直接退出循环，没有任何输出，导致用例执行错误，这是第10个测试用例报错的最可能原因。

2. 存在变量遮蔽的不规范写法 #

外层已经定义了int x = 0，输入的for循环中又重新定义了int x，虽然逻辑上这个错误不会影响最终执行结果（输入循环的局部x销毁后，外层x初始值为0刚好符合后续遍历的要求），但属于非常不规范的写法，极易引发逻辑错误。

3. 动态内存未释放 #

你通过new申请的动态数组没有调用delete[]释放，会造成内存泄漏，虽然大部分OJ平台不会检测内存泄漏，但属于代码规范问题。

4. 时间复杂度可优化 #

当前排序的时间复杂度为O(nlogn)，对于本题可以用求和法（计算1到n的和减去所有输入数的和，结果就是缺失值），时间复杂度为O(n)，空间复杂度为O(1)，不需要申请数组，效率更高。

修正后代码示例 #

#include <iostream>
using std::cin;
using std::cout;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    long long total = static_cast<long long>(n) * (n + 1) / 2;
    long long sum = 0;
    for (int i = 0; i < n - 1; i++)
    {
        int num;
        cin >> num;
        sum += num;
    }
    cout << total - sum << '\n';
    return 0;
}

内容的提问来源于stack exchange，提问作者golden_hacker