c++ - 想出解决方案？

Question

给出了一个由 N 个不同的整数组成的零索引数组 A。该数组包含 [1..(N + 1)] 范围内的整数，这意味着正好缺少一个元素。

您的目标是找到缺失的元素。

写一个函数:

int solution(int A[], int N); 

给定一个零索引数组 A，返回缺失元素的值。

例如，给定数组 A 使得:

A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5

函数应该返回 4，因为它是缺少的元素。

假设:

N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].

复杂度:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

它不适用于有两个元素的情况

int solution(vector<int> &A) {

    sort(A.begin(), A.end());
    int missingIndex = 0;

    for (int i = 0; i < A.size(); i++)
    {
        if ( i != A[i]-1)
        {
            missingIndex = i+1;
        }

    }
    return missingIndex;
}

Answer 1

由于您的数组是零索引的并且数字是从 1 到 N+1，因此语句应该是:

if ( i != A[i]-1)

此外，您应该在更新 missingIndex 后立即跳出 for 循环，因为缺失元素之外的所有条目都应具有 (i != A[i]-1)

此外，由于排序，您的解决方案是 O(NlogN) 而不是 O(N)。

相反，您可以对数组 (使用 unsigned long long int) 中的所有元素求和，并检查它与 N(N+1)/2 的区别