Số đơn lẻ III (Single Number III) trong C++

Mô tả bài toán

Cho mảng có đúng 2 phần tử xuất hiện 1 lần, các phần tử còn lại xuất hiện 2 lần. Tìm 2 phần tử duy nhất đó.

Ví dụ: [1,2,1,3,2,5] → [3,5].

Giải thuật XOR + Phân chia theo bit

1. XOR tất cả phần tử → xor_all = a ^ b (a,b là 2 số tìm).
2. Tìm bit pos bất kỳ mà xor_all có bit 1 (a và b khác nhau ở bit này).
3. Chia mảng thành 2 nhóm theo bit pos: nhóm 1 có bit đó = 1, nhóm 2 = 0. a,b rơi vào 2 nhóm khác nhau.
4. XOR từng nhóm riêng biệt → được a và b.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vec(vector<int> v) {
    cout << "[";
    for (int x : v) cout << x << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xor_all = 0;
        for (int x : nums) xor_all ^= x;
        int pos = 0;
        while ((xor_all & (1 << pos)) == 0) pos++;
        int a = 0;
        for (int x : nums) {
            if (x & (1 << pos)) a ^= x;
        }
        int b = xor_all ^ a;
        return {a, b};
    }
};

int main() {
    vector<int> v = {1,2,1,3,2,5};
    Solution ob;
    print_vec(ob.singleNumber(v)); // [3, 5]
    return 0;
}

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(1).