Single Number II: หาตัวเลขที่ปรากฏครั้งเดียวใน Array (อื่นๆ ปรากฏ 3 ครั้ง)

โจทย์

กำหนด array ของจำนวนเต็มไม่ว่าง ทุกตัวเลขปรากฏ 3 ครั้ง ยกเว้นตัวเดียวที่ปรากฏ 1 ครั้ง หาตัวเลขตัวนั้น

ตัวอย่าง: [2,2,3,2] → Output: 3

วิธีแก้: Bit Manipulation (การนับบิต)

เนื่องจากทุกตัวเลขปรากฏ 3 ครั้ง บิตแต่ละตำแหน่งที่รวมกันจะหาร 3 ลงตัว ยกเว้นบิตของตัวเลขที่ปรากฏ 1 ครั้ง

ขั้นตอนอัลกอริทึม

1. หา max_num = ค่าสัมบูรณ์สูงสุดใน array
2. คำนวณ max_bits = จำนวนบิตที่จำเป็น (floor(log2(max_num)) + 2 สำหรับ sign bit)
3. สร้าง array bit_count ขนาด max_bits เก็บจำนวนบิต 1 ในแต่ละตำแหน่ง
4. วนลูปทุกตัวเลข: นับบิต 1 ในแต่ละตำแหน่ง (ใช้ bitwise & 1 และ >>= 1)
5. ทำ modulo 3 ทุกตำแหน่งบิต (เหลือบิตของตัวเลขที่ปรากฏ 1 ครั้ง)
6. สร้างผลลัพธ์จากบิตที่เหลือ
7. จัดการ negative number (ถ้าบิต sign = 1)

การติดตั้ง (Python Implementation)

import math

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        # 1. หาค่าสูงสุด (absolute) เพื่อกำหนดจำนวนบิต
        max_num = max(map(abs, nums))
        max_bits = int(math.log2(max_num)) + 2 if max_num > 0 else 1
        
        # 2. นับบิตในแต่ละตำแหน่ง
        bit_count = [0] * max_bits
        
        for num in nums:
            # จัดการ negative ด้วย two's complement concept
            # ใช้ unsigned representation สำหรับนับบิต
            n = num & ((1 << max_bits) - 1)  # mask ให้อยู่ในช่วง max_bits
            for i in range(max_bits):
                if n & 1:
                    bit_count[i] += 1
                n >>= 1
        
        # 3. Modulo 3 เพื่อเอาเฉพาะบิตของตัวเลขที่ unique
        for i in range(max_bits):
            bit_count[i] %= 3
        
        # 4. สร้างผลลัพธ์
        result = 0
        for i in range(max_bits):
            if bit_count[i]:
                result |= (1 << i)
        
        # 5. จัดการ negative (ถ้าบิต sign = 1)
        if bit_count[max_bits - 1]:
            result -= (1 << max_bits)
        
        return result

# ทดสอบ
ob = Solution()
print(ob.singleNumber([2, 2, 3, 2]))           # 3
print(ob.singleNumber([0, 1, 0, 1, 0, 1, 99])) # 99
print(ob.singleNumber([-2, -2, -2, -3]))       # -3

Output

3
99
-3

วิธีแก้แบบ Simple (ใช้ Counter) - O(n) space

from collections import Counter

def singleNumber_simple(nums):
    count = Counter(nums)
    for num, freq in count.items():
        if freq == 1:
            return num

วิธีแก้ Bitwise ขั้นสูง (O(1) space, ไม่ต้อง loop บิต) - สำหรับ positive numbers

def singleNumber_bitwise(nums):
    ones, twos = 0, 0
    for num in nums:
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
    return ones

หมายเหตุ: วิธีนี้ซับซ้อนกว่า และต้องปรับสำหรับ negative numbers

สรุป

วิธี Bit Counting เข้าใจง่าย จัดการ negative ได้ และใช้ space O(1) (คงที่) เหมาะสำหรับสัมภาษณ์และการทำความเข้าใจหลักการ bit manipulation

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ