Single Element in a Sorted Array ใน C++

ตัวอย่าง: nums = [1, 1, 2, 3, 3, 4, 4, 8, 8] → ผลลัพธ์: 2

วิธีที่ 1: XOR (ทำงานได้กับอาร์เรย์ไม่เรียงลำดับด้วย)

คุณสมบัติของ XOR: a ^ a = 0, a ^ 0 = a, a ^ b ^ a = b

XOR ทุกตัวในอาร์เรย์ → คู่ที่ซ้ำกันจะโดน cancel ออก เหลือตัวเดี่ยว

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

ความซับซ้อน:

• เวลา: O(n)
• พื้นที่: O(1)

วิธีที่ 2: Binary Search (ใช้ข้อเท็จจริงว่า sorted + pairs)

เนื่องจากอาร์เรย์เรียงลำดับและเป็นคู่คู่ ตำแหน่งของคู่ปกติคือ (even, odd) = (2k, 2k+1)

หากไม่มีตัวเดี่ยว: nums[2k] == nums[2k+1] สำหรับทุก k

ตัวเดี่ยวจะทำให้คู่หลังจากมัน shift: (odd, even) = (2k+1, 2k+2)

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // ทำให้ mid เป็นเลขคู่เสมอ (เพื่อเปรียบเทียบกับ mid+1)
            if (mid % 2 == 1) mid--;
            
            if (nums[mid] == nums[mid + 1]) {
                // คู่นี้ปกติ ตัวเดี่ยวอยู่ขวา
                left = mid + 2;
            } else {
                // คู่นี้ผิดปกติ ตัวเดี่ยวอยู่ซ้าย (รวม mid)
                right = mid;
            }
        }
        return nums[left];
    }
};

ความซับซ้อน:

• เวลา: O(log n)
• พื้นที่: O(1)

ตัวอย่างโค้ด C++ (วิธี XOR - เรียบง่าย)

#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) << endl;
    return 0;
}

Input

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

Output

2

สรุป: วิธี XOR เรียบง่าย O(n) ใช้ได้ทุกกรณี (ไม่ต้อง sorted) วิธี Binary Search O(log n) ใช้ได้เฉพาะ sorted array และเป็น follow-up ที่ดีสำหรับสัมภาษณ์