ข้อ 68 · LC136 Single Number (ตัวเลขที่ไม่ซ้ำ) 🟢

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

หา element เดียวที่ปรากฏครั้งเดียวใน array ด้วย XOR ในเวลา O(n) และ memory O(1)

โจทย์ (LC136): กำหนด array จำนวนเต็มที่ไม่ว่างเปล่าชื่อ nums โดยทุก element ปรากฏสองครั้ง ยกเว้น element เดียวที่ปรากฏเพียงครั้งเดียว ให้หา element ที่ไม่ซ้ำนั้น โดยต้อง implement solution ที่ทำงานในเวลา linear runtime (O(n)) และใช้ extra space คงที่ (O(1)) เท่านั้น

Example 1

Input:: nums = [2, 2, 1]
Output:: 1
Explanation:: 2 กับ 2 จับคู่ซ้ำกัน เหลือ 1 เป็นตัวที่ไม่ซ้ำ

Example 2

Input:: nums = [4, 1, 2, 1, 2]
Output:: 4
Explanation:: 1 กับ 2 ต่างก็ปรากฏสองครั้ง เหลือ 4 เป็นตัวที่ไม่ซ้ำ

Example 3

Input:: nums = [1]
Output:: 1
Explanation:: มีสมาชิกตัวเดียวในอาร์เรย์ ถือเป็นตัวที่ไม่ซ้ำโดยอัตโนมัติ

Constraints (ข้อจำกัด)

1 <= nums.length <= 3 × 10^4
-3 × 10^4 <= nums[i] <= 3 × 10^4
ทุกตัวโผล่สองครั้ง ยกเว้นตัวเดียวที่โผล่ครั้งเดียว
ท้าทาย: ต้อง O(n) time และ O(1) extra space

เงื่อนไข

โจทย์ขอให้ทำในเวลา O(n) และใช้ memory เพิ่มแค่ O(1) และรับประกันว่ามีตัวเดี่ยวเพียงตัวเดียวเสมอ

แนวทาง — ต้องใช้อะไร & คิดยังไง

ข้อนี้ใช้คุณสมบัติของ XOR โดยตรง คือ a ^ a = 0 (เลขเดียวกัน XOR กันได้ 0) และ a ^ 0 = a (XOR กับ 0 ได้ตัวเดิม) และ XOR สลับลำดับได้

วิธีธรรมดาคือใช้ hash map (dict) หรือ hash set นับ frequency (ความถี่) แต่ละตัว แล้วหาตัวที่นับได้ 1 ซึ่งถูกต้องแต่ต้องใช้ memory เพิ่ม O(n) ไม่ผ่านเงื่อนไข O(1) ของโจทย์ ถ้าเอาทุกตัวมา XOR กันหมดแทน คู่ที่ซ้ำกันจะหักล้างเป็น 0 เหลือแต่ตัวที่ไม่ซ้ำ โดยไม่ต้องเก็บอะไรเลย

initialize ตัวแปรสะสม result = 0
iterate ทุก element n ใน array แล้ว XOR เข้ากับ result (result ^= n)
เมื่อจบ คู่ที่ซ้ำหักล้างกันหมด result จึงเหลือค่าตัวที่ไม่ซ้ำ return result

จุดพลาดที่พบบ่อย

วิธี XOR นี้ใช้ได้เพราะมีตัวเดี่ยวเพียงตัวเดียว ถ้าโจทย์เปลี่ยนเป็นมีตัวเดี่ยวหลายตัวหรือตัวที่ซ้ำ 3 ครั้ง จะใช้วิธีนี้ตรง ๆ ไม่ได้ ต้องเปลี่ยนเทคนิค

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n   # ตัวที่ซ้ำกันจะ xor กันหายเป็น 0 เหลือแต่ตัวเดี่ยว
    return result

print(single_number([2, 2, 1]))        # 1
print(single_number([4, 1, 2, 1, 2]))  # 4

Output

1
4

เพราะ XOR สลับลำดับได้และจับคู่กันเองหักล้างเป็น 0 ไม่ว่า array จะเรียงยังไง เมื่อ XOR ทุกตัวเข้าด้วยกัน คู่ที่เหมือนกันทุกคู่จะกลายเป็น 0 หมด (a ^ a = 0) แล้ว 0 ^ x ก็ได้ x เอง จึงเหลือแต่ตัวที่ปรากฏครั้งเดียว

เสน่ห์ของวิธีนี้คือไม่ต้องใช้ hash set หรือ hash map มาเก็บนับ frequency เลย จึงประหยัด memory เป็น O(1) จริง ๆ ถ้าเปลี่ยนไปใช้ hash map นับ frequency จะได้คำตอบเหมือนกันแต่กิน memory O(n)

Time O(n) iterate XOR รอบเดียว · Space O(1) ใช้ตัวแปรสะสมตัวเดียว

💡 สรุป pattern

เจอโจทย์ที่ของมาเป็นคู่ ๆ แล้วเหลือตัวแปลก ให้นึกถึง XOR ทันที มันหักล้างคู่ที่ซ้ำได้ฟรีโดยไม่ใช้ memory เพิ่ม