資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 中的單數 III
假設我們有一個數組，其中正好有兩個元素只出現一次，而其他元素都出現兩次。所以我們必須定義一個函式，該函式將找到這兩個數字。因此，如果給定的陣列像 [1,2,3,1,5,2] 這樣，則輸出將是 [3, 5]。
為了解決這個問題，我們將遵循以下步驟 -
異或_結果 := 0
對於 i 在 nums 的大小的範圍內，
異或_結果 := 異或_結果 XOR nums[i]
pos := 0
當異或_結果 AND 2^pos = 0 時，
pos 增加 1
num1 := 0
對於 i 在 nums 的大小的範圍內 – 1，
如果 nums[i] 和 2 ^ pos 不為 0，那麼
num1 := num1 XOR num[i]
num2 := 異或_結果 XOR num1
返回 num1 和 num2
示例 (C++)
為了更好地理解，我們來看看以下實現 -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector <int> singleNumber(vector<int>& nums) {
int xor_result = 0;
for (int i=0;i < nums.size(); i++) {
xor_result = xor_result ^ nums[i];
}
int pos = 0;
while ((xor_result & (1 << pos)) == 0) {
pos++;
}
int num1 = 0;
for (int i=0;i < nums.size(); i++) {
if ((nums[i] & (1 << pos)) != 0) {
num1 = num1 ^ nums[i];
}
}
int num2 = xor_result ^ num1;
vector<int> result = {num1, num2};
return result;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1,3,2,5};
print_vector(ob.singleNumber(v));
}輸入
[1,2,1,3,2,5]
輸出
[3, 5, ]
更新於: 02-5 月-2020
348 檢視
廣告