Giả sử chúng ta có một mảng, có đúng hai phần tử xuất hiện một lần, nhưng những phần tử khác xuất hiện hai lần. Vì vậy, chúng ta phải xác định một hàm, mà sẽ tìm thấy hai số này. Vì vậy, nếu mảng đã cho giống như [1,2,3,1,5,2], thì đầu ra sẽ là [3, 5].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
xor_res:=0
-
cho tôi trong phạm vi từ 0 đến kích thước của nums
-
xor_res:=xor_res XOR nums [i]
-
-
pos:=0
-
while xor_res AND 2 ^ pos =0, do,
-
tăng vị trí lên 1
-
-
num1:=0
-
cho tôi trong phạm vi từ 0 đến kích thước của nums - 1
-
nếu nums [i] và 2 ^ pos không phải là 0, thì
-
num1:=num1 XOR num [i]
-
-
-
num2:=xor_res XOR num1
-
trả về num1 và num2
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
[1,2,1,3,2,5]
Đầu ra
[3, 5, ]