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

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是缺失在第一个数组中的元素。

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

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

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

输出:

缺失的元素是 1

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

辅助空间: O(1), 不需要额外的空间,所以是个常数。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例