두 개의 배열 A와 B가 있고 배열 A에 n개의 요소가 있다고 가정합니다. 두 번째 배열 B에는 A의 모든 요소가 있지만 섞이고 하나의 요소가 제거됩니다. 누락된 요소를 찾아야 합니다. 따라서 A =[4, 8, 1, 3, 7]이고 B =[7, 4, 3, 1]이면 출력은 8입니다.
이것은 XOR 트릭을 사용하여 해결할 수 있습니다. 각 요소의 결합된 발생은 A에서 한 번, A에서 한 번만 발생하는 한 요소를 제외하고 B에서 두 번 발생합니다. x XOR x =0이라는 것을 알고 있으므로 두 요소 모두에서 XOR을 수행하면 배열. 결과에 숫자가 누락됩니다.
예
#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