寻找数组缺失元素的算法疑问：为何不能采用直接比对法？

给定整数N和一个长度为N-1的数组，数组包含1到N中的N-1个不重复数字，需要找出1到N里没出现在数组中的那个数字。

导师的O(n²)解法 #

我的导师用双重循环的线性搜索实现了这个功能，时间复杂度为O(n²)，代码如下：

// 外层循环遍历1到N的所有数字
for (int i = 1; i <= N; i++) {
    // 标记当前数字是否在数组中存在
    int flag = 0;

    // 内层循环线性搜索数组
    for (int j = 0; j < N - 1; j++) {
        if (a[j] == i) {
            // 找到数字，标记为存在
            flag = 1;
            break;
        }
    }

    // 如果标记为0，说明当前数字缺失，返回它
    if (flag == 0) return i;
}

我的疑问与代码 #

我搞不懂为什么不能直接遍历数组，对比下标对应的预期值？我写的代码如下：

for (int i = 0; i < n; i++) {
   if (a[i] != i + 1) {
      return i;
      break;
   }
}

问题出在哪？ #

你的代码逻辑只有在数组严格按1、2、3……N的顺序排列时才会生效，但题目根本没说数组是有序的！

举个例子：假设N=5，数组是[2,1,4,5]，缺失的数字是3。按你的代码遍历：

• 当i=0时，a[0]=2，i+1=1，两者不相等，你会直接返回0，这明显错误——缺失的是3，不是0。

题目只保证数组包含1到N中的N-1个数字，没规定顺序，所以你的解法不适用所有情况。

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