Single Element in a Sorted Array trong C++

Cho mảng đã sắp xếp, mọi phần tử xuất hiện đúng 2 lần trừ một phần tử xuất hiện 1 lần. Tìm phần tử đơn lẻ đó.

Ví dụ: [1,1,2,3,3,4,4,8,8] → output 2.

Giải thuật (XOR)

Vì a ^ a = 0 và 0 ^ b = b, XOR tất cả phần tử sẽ cho ra phần tử đơn lẻ.

• ans = 0.
• Duyệt mảng: ans ^= nums[i].
• Trả về ans.

Ví dụ code

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

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int ans = 0;
        for (int x : nums) ans ^= x;
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,1,2,3,3,4,4,8,8};
    cout << ob.singleNonDuplicate(v);
    return 0;
}

Input

[1,1,2,3,3,4,4,8,8]

Output

2