สมมติว่าเรามีอาร์เรย์ มีองค์ประกอบสองอย่างปรากฏเพียงครั้งเดียว แต่มีองค์ประกอบอื่นปรากฏขึ้นสองครั้ง เราต้องนิยามฟังก์ชัน ที่จะหาเลขสองตัวนี้ ดังนั้นหากอาร์เรย์ที่กำหนดเป็นเหมือน [1,2,3,1,5,2] ผลลัพธ์จะเป็น [3, 5]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
xor_res :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของ nums
-
xor_res :=xor_res XOR nums[i]
-
-
ตำแหน่ง :=0
-
ในขณะที่ xor_res AND 2^pos =0, ทำ
-
เพิ่มตำแหน่งขึ้น 1
-
-
num1 :=0
-
สำหรับฉันในช่วง 0 ถึงขนาดของ nums – 1
-
ถ้า nums[i] และ 2 ^ pos ไม่ใช่ 0 แล้ว
-
num1 :=num1 XOR num[i]
-
-
-
num2 :=xor_res 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, ]
