資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時裝研究
法律研究在另一個亂序複製的陣列中查詢缺失的數字（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 次瀏覽
廣告