C++程序从重复数组中查找缺失元素

给定两个除一个元素外的相互重复的数组，需要找到缺失的元素。

例子：

Input:  arr1[] = {1, 4, 5, 7, 9}
        arr2[] = {4, 5, 7, 9}
Output: 1
1是缺失在第二个数组中的元素。

Input: arr1[] = {2, 3, 4, 5}
       arr2[] = {2, 3, 4, 5, 6}
Output: 6
6是缺失在第一个数组中的元素。

一种 简单的解决方法 是遍历数组并逐个检查元素，并在找到不匹配元素时标记缺失元素，但这种解决方法需要线性时间超过数组大小。

另一种 高效的解决方法 是基于二分搜索方法。算法步骤如下:

在更大的数组中开始二分搜索，并将mid设为(lo + hi) / 2
如果两个数组的值相同，则缺失元素必须在右半部分，因此将lo设置为mid
否则，如果mid元素不相等，则将hi设置为mid，因为较大数组中缺失的元素必须在左半部分。
分别处理单个元素和零元素数组的特殊情况，单个元素本身将是缺失的元素。如果第一个元素本身不相等，则该元素将是缺失的元素。/li>

下面是上述步骤的实现

// 从相同的数组中查找缺失的元素（除一个缺失的元素外）
#include <bits/stdc++.h>
using namespace std;
  
// 基于二分搜索方法查找缺失元素。arr1[]的大小为N。假设arr1[]和arr2[]的顺序是相同的。
int findMissingUtil(int arr1[], int arr2[], int N)
{
    //特殊情况，仅为第二个数组缺失的元素
    if (N == 1)
        return arr1[0];
  
    //特殊情况，第一个元素缺失
    if (arr1[0] != arr2[0])
        return arr1[0];
  
    //初始化当前的端点
    int lo = 0, hi = N - 1;
  
    //循环直到lo < hi
    while (lo < hi)
    {
        int mid = (lo + hi) / 2;
  
        // 如果mid索引处的元素相等，则转到右子数组
        if (arr1[mid] == arr2[mid])
            lo = mid;
        else
            hi = mid;
  
        //如果lo, hi变为连续，则打破
        if (lo == hi - 1)
            break;
    }
  
    //缺失的元素将在更大的数组的hi索引处
    return arr1[hi];
}
  
// 这个函数主要进行基本的错误检查并调用findMissingUtil函数
void findMissing(int arr1[], int arr2[], int M, int N)
{
    if (N == M-1)
        cout    << "缺失元素是 "
        << findMissingUtil(arr1, arr2, M) << endl;
    else if (M == N-1)
        cout << "缺失元素是 "
        << findMissingUtil(arr2, arr1, N) << endl;
    else
        cout << "无效的输入";
}
  
// 主函数
int main()
{
    int arr1[] = {1, 4, 5, 7, 9};
    int arr2[] = {4, 5, 7, 9};
  
    int M = sizeof(arr1) / sizeof(int);
    int N = sizeof(arr2) / sizeof(int);
  
    findMissing(arr1, arr2, M, N);
  
    return 0;
}

输出：

缺失元素是 1

时间复杂度： O(logM + logN)，其中M和N表示给定的两个数组的大小。

辅助空间： O(1)，不需要额外的空间，因此是一个常量。

如果输入的数组顺序不同怎么办？

在这种情况下，缺失的元素就是两个数组中所有元素的异或值。感谢Yolo Song的建议。

// C++程序查找一个数组中缺失的元素，
// 它包含其他数组的所有元素，除了一个。
// 两个数组中的元素可以是任意顺序。
#include <bits/stdc++.h>
using namespace std;
  
// 该函数主要执行arr1[]和arr2[]中所有元素的XOR
void findMissing(int arr1[], int arr2[], int M,
                 int N)
{
    if (M != N-1 && N != M-1)
    {
        cout << "无效的输入";
        return;
    }
  
    // 执行所有元素的XOR
    int res = 0;
    for (int i=0; i<M; i++)
       res = res^arr1[i];
    for (int i=0; i<N; i++)
       res = res^arr2[i];
  
    cout << "缺失的元素是 " << res;
}
  
// 主函数
int main()
{
    int arr1[] = {4, 1, 5, 9, 7};
    int arr2[] = {7, 5, 9, 4};
  
    int M = sizeof(arr1) / sizeof(int);
    int N = sizeof(arr2) / sizeof(int);
  
    findMissing(arr1, arr2, M, N);
  
    return 0;
}