在另一个乱序复制的数组中查找缺失的数字(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
广告