从C ++中的重复数组中查找丢失的元素

Z时代
2024-01-10
分类：综合

概念

对于给定的两个数组，除了一个元素外，它们彼此重复，这意味着该数组之一中的一个元素丢失了，我们的任务是确定该丢失的元素。

输入值

arr1[] = {2, 5, 6, 8, 10}
arr2[] = {5, 6, 8, 10}

输出结果

第二个数组缺少2个。

输入值

arr1[] = {3, 4, 5, 6}
arr2[] = {3, 4, 5, 6, 7}

输出结果

第一个数组缺少7个。

方法

在这里，我们应用了一种简单的解决方案，其中我们遍历数组并逐个元素验证并在检测到不匹配项时标记缺少的元素。但是这种解决方案的缺点是，它需要整个数组大小的线性时间。

我们可以实现另一种基于二进制搜索方法的有效解决方案。我们遵循以下算法，逐步解释-

在更大的数组中开始二进制搜索，并以（low + high）/ 2作为中间值
已经看到，如果两个数组中的值相同，则缺少的元素必须在右侧，因此将低标记为中
如果中部元素不相同，则缺失元素中的其他高标记必须位于较大数组的左侧。
我们必须分别处理特殊情况，因为对于单个元素和零元素数组，单个元素本身将是缺少的元素。

已经观察到，如果第一个元素本身不相等，则该元素将成为丢失的元素。

示例

// C++ program to find missing element from same
//数组（一个缺少的元素除外）
#include <bits/stdc++.h>
using namespace std;
//显示函数以根据二进制确定缺少的元素
//搜索方法。arrA []的大小较大，并且
//Q是它的大小。假设arrA []和arrB []
//以相同的顺序。
int findMissingUtil(int arrA[], int arrB[], int Q){
   //元素
   //在第二个数组中丢失
   if (Q == 1)
      return arrA[0];
   //考虑特殊情况，因为缺少第一个元素
   if (arrA[0] != arrB[0])
      return arrA[0];
   //用于初始化当前角点
   int low = 0, high = Q - 1;
   // Iterate until low < high
   while (low < high){
      int mid = (low + high) / 2;
      //已经观察到，如果中间索引处的元素相等
      //然后去右边的子数组
      if (arrA[mid] == arrB[mid])
         low = mid;
      else
         high = mid;
         //因此，如果低，高变为连续，则中断
      if (low == high - 1)
      break;
   }
   //高索引处
   //大数组
   return arrA[high];
}
//所以这个功能主要做基本的错误检查
//并调用findMissingUtil-
void findMissing(int arrA[], int arrB[], int P, int Q){
   if (Q == P-1)
      cout << "Missing Element is "
      << findMissingUtil(arrA, arrB, P) << endl;
   else if (P == Q-1)
      cout << "Missing Element is "
      << findMissingUtil(arrB, arrA, Q) << endl;
   else
   cout << "Invalid Input";
}
//驱动程式码
int main(){
   int arrA[] = {2, 5, 6, 8, 10};
   int arrB[] = {5, 6, 8, 10};
   int P = sizeof(arrA) / sizeof(int);
   int Q = sizeof(arrB) / sizeof(int);
   findMissing(arrA, arrB, P, Q);
   return 0;
}