資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究在 C++ 中查詢 2n+1 個整數元素陣列中的單個元素
在這個問題中，我們得到一個包含 (2n+1) 個整數值的陣列。在所有這些值中，n 個元素在陣列中出現兩次，並且陣列中只有一個元素出現一次。我們的任務是在 2n+1 個整數元素的陣列中查詢單個元素。
讓我們舉個例子來理解這個問題：
輸入
arr[] = {1, 3, 5, 6, 5, 1, 3}輸出
5
解決方案方法
解決這個問題的一個簡單方法是使用元素計數器。如果遇到一個元素，則儲存其值和出現次數。之後，在表中搜索出現次數 = 1 的元素。更高效的解決方案是使用異或 (XOR)。在這裡，我們將對陣列的所有元素執行異或運算。這個異或運算將使所有出現兩次的元素變為 0。而唯一存在的元素值是出現次數為 1 的元素。
這是因為異或的特性：
- a^a = 0 - a^0 = a
程式演示了我們解決方案的工作原理：
示例
#include <iostream>
using namespace std;
int findSingleValue(int arr[], int n) {
int element = 0;
for (int i = 0; i < n; i++)
element = element ^ arr[i];
return element;
}
int main() {
int arr[] = { 1, 3, 5, 6, 5, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The element of the array with single occurrence is "<<findSingleValue(arr, n);
return 0;
}輸出
The element of the array with single occurrence is 6
更新於：2021-3-16
234 次瀏覽
廣告