数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在C++中查找重复数组中丢失的元素
概念
给定两个数组，它们互为副本，只有一个元素除外，这意味着一个数组中缺少一个元素，我们的任务是确定该丢失的元素。
输入
arr1[] = {2, 5, 6, 8, 10}
arr2[] = {5, 6, 8, 10}输出
2
第二个数组缺少2。
输入
arr1[] = {3, 4, 5, 6}
arr2[] = {3, 4, 5, 6, 7}输出
7
第一个数组缺少7。
方法
在这里，我们采用一个简单的解决方案，我们遍历数组并逐个元素进行验证，并在检测到不匹配时标记丢失的元素。但是，此解决方案的缺点是它需要线性时间才能遍历数组。
我们可以实现另一个基于二分查找方法的高效解决方案。我们遵循以下逐步解释的算法：
- 在较大的数组中开始二分查找，并将中间值设置为 (low + high) / 2
- 如果两个数组的值相同，则丢失的元素必须在右侧，因此将low设置为mid
- 否则，将high设置为mid，因为如果中间元素不同，则丢失的元素必须在较大数组的左侧。
- 我们必须分别处理特殊情况，因为对于单元素和零元素数组，单元素本身就是丢失的元素。
如果第一个元素本身不相等，则该元素将是丢失的元素。
示例
// C++ program to find missing element from same
// arrays (except one missing element)
#include <bits/stdc++.h>
using namespace std;
// Shows function to determine missing element based on binary
// search approach. arrA[] is of larger size and
// Q is size of it. arrA[] and arrB[] are assumed
// to be in same order.
int findMissingUtil(int arrA[], int arrB[], int Q){
// Considers special case, for only element which is
// missing in second array
if (Q == 1)
return arrA[0];
// Considers special case, for first element missing
if (arrA[0] != arrB[0])
return arrA[0];
// Used to initialize current corner points
int low = 0, high = Q - 1;
// Iterate until low < high
while (low < high){
int mid = (low + high) / 2;
// It has been observed that if element at mid indices are equal
// then go to right subarray
if (arrA[mid] == arrB[mid])
low = mid;
else
high = mid;
// So if low, high becomes contiguous, break
if (low == high - 1)
break;
}
// Now missing element will be at high index of
// bigger array
return arrA[high];
}
// So this function mainly does basic error checking
// and calls 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";
}
// Driver Code
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;
}输出
Missing Element is 2
更新于：2020年7月24日
101 次查看
广告