在另一个乱序复制的数组中查找缺失的数字(C++ 版)


假设我们有两个数组 A 和 B,数组 A 有 n 个元素。第二个数组 B 中含有 A 中的所有元素,但它们被重新排列,并且移除了一个元素。我们要找出缺失的元素。因此,如果 A = [4, 8, 1, 3, 7],并且 B = [7, 4, 3, 1],则输出为 8。

这个问题可以通过使用异或技巧来解决。每种元素的组合出现两次,一次在 A 中,另一次在 B 中,除了一种元素只在 A 中出现一次。我们知道 x XOR x = 0,因此如果我们对这两个数组中的元素执行异或,则结果就是缺少的数字。

示例

 实时演示

#include<iostream>
using namespace std;
int FindMissingElement(int A[], int B[], int n) {
   int min_element = 0;
   for (int i = 0; i < n; i++)
   min_element = min_element ^ A[i];
   for (int i = 0; i < n - 1; i++)
   min_element = min_element ^ B[i];
   return min_element;
}
int main() {
   int A[] = {4, 8, 1, 3, 7};
   int B[] = {7, 4, 3, 1};
   int n = sizeof(A) / sizeof(A[0]);
   cout << "Missing element: " << FindMissingElement(A, B, n);
}

输出

Missing element: 8

更新于:2019-12-18

277 次浏览

开启您的 职业生涯

完成课程,获得认证

开始学习
广告