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;
}
输出:
缺失的元素是 1
时间复杂度: O(M + N), 其中M和N表示给定的两个数组的大小。
辅助空间: O(1), 不需要额外的空间,所以是个常数。