LeetCode #136 Single Number: ผึ้ง เป็ด กระต่าย แพนด้า หาเลขโสดตัวเดียวในฝูงคู่

โจทย์ Single Number #136 ให้ลิสต์ตัวเลขที่ “ทุกตัวมีคู่ซ้ำ 2 ครั้ง ยกเว้นตัวเดียว” ให้หาตัวโสดนั้น เช่น [4,1,2,1,2] คำตอบคือ 4 และโจทย์ท้าว่าให้ทำเวลา O(n) โดยใช้หน่วยความจำเพิ่มคงที่

ในชีวิตจริงมันคือการหาถุงเท้าข้างที่หายคู่ในตะกร้าผ้าที่เพิ่งออกจากเครื่องซักผ้า ถุงเท้าที่จับคู่ได้ก็พับเก็บ เหลือข้างเดียวที่ไม่มีคู่ นั่นแหละคำตอบ

รอบนี้ไม่ใช่ผมอธิบายครับ ให้สัตว์ 4 ตัวสู้กันคนละวิธี แล้ว บารอน สิงโตทะเลใส่โค้ทตัดสินด้วยตัวเลขจากเครื่องนี้

ผู้เข้าแข่งขัน

ตัวละคร	วิธี	นิสัยที่เข้ากับวิธี
ผึ้งนักบัญชี	นับจำนวนด้วย dict / Counter	จดทุกอย่างลงสมุด
เป็ดเข้าแถว	เรียงลำดับแล้วดูทีละคู่	ชอบความเป็นระเบียบ
กระต่ายนักคณิต	สูตร `2*sum(set) - sum`	หาทางลัดด้วยเลข
แพนด้าจับคู่ถุงเท้า	XOR ทุกตัว	ไม่จดอะไรเลย จับคู่หักล้างในหัว
บารอน	กรรมการ	ดูตัวเลขจริงก่อนพูด

วิธีที่ 1: ผึ้งนักบัญชี — นับด้วย Counter

ผึ้งเดินดูทีละตัว จดว่าเลขไหนเจอกี่ครั้ง แล้วหาตัวที่นับได้ 1 ใน Python ใช้ collections.Counter ได้เลย

เวลา: O(n) โดยเฉลี่ย
หน่วยความจำเพิ่ม: O(n) — สมุดต้องจดเลขเกือบครึ่งลิสต์
ข้อดี: ใช้กับโจทย์ดัดแปลงได้ทันที เช่น “ทุกตัวซ้ำ 3 ครั้ง ยกเว้นตัวเดียว”
ข้อเสีย: ไม่ผ่านข้อท้าเรื่องหน่วยความจำคงที่

วิธีที่ 2: เป็ดเข้าแถว — เรียงแล้วดูทีละคู่

เป็ดเรียงลิสต์ แล้วดูช่อง 0-1, 2-3, 4-5 … ถ้าคู่ไหนไม่เท่ากัน ตัวแรกของคู่นั้นคือคำตอบ ถ้าเจอครบทุกคู่ ตัวสุดท้ายคือคำตอบ

เวลา: O(n log n) เพราะการเรียง
หน่วยความจำเพิ่ม: O(n) ถ้าใช้ sorted() หรือ O(1) ถ้าเรียงในที่ (แต่แก้ข้อมูลเดิม)
ข้อดี: ไม่ต้องรู้เทคนิคพิเศษ ดีบักง่าย เพราะเห็นคู่เรียงกัน
ข้อเสีย: ช้ากว่าวิธี O(n) และแก้ลิสต์เดิมถ้าเรียงในที่

วิธีที่ 3: กระต่ายนักคณิต — สูตรผลรวม

กระต่ายคิดว่า ถ้าทุกตัวมีคู่ ผลรวมของ “เลขที่ไม่ซ้ำ” คูณ 2 จะเท่ากับผลรวมทั้งลิสต์ ส่วนต่างที่เกินมาก็คือเลขโสด: 2 * sum(set(nums)) - sum(nums)

เวลา: O(n)
หน่วยความจำเพิ่ม: O(n) — set เก็บเลขไม่ซ้ำ
ข้อดี: บรรทัดเดียว อ่านแล้วเข้าใจได้ด้วยเลข ป.6
ข้อเสีย: ภาษาที่ int มีขนาดจำกัด (Java/C++) ผลรวมอาจล้น Python ไม่มีปัญหานี้เพราะ int ขยายได้

วิธีที่ 4: แพนด้าจับคู่ถุงเท้า — XOR

XOR (เขียนว่า ^ ใน Python) คือการเทียบบิตทีละตำแหน่ง บิตเหมือนกันได้ 0 ต่างกันได้ 1 มีกฎสองข้อที่แพนด้าใช้:

a ^ a = 0        (เลขเดียวกันหักล้างกันเหมือนถุงเท้าคู่หนึ่งพับเก็บ)
a ^ 0 = a        (XOR กับ 0 ไม่เปลี่ยนอะไร)
ลำดับไม่สำคัญ     4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4

แพนด้าจึงไล่ XOR ทุกตัวสะสมไว้ในตัวแปรเดียว คู่ทั้งหมดหักล้างกันหายไป เหลือตัวโสด

เวลา: O(n)
หน่วยความจำเพิ่ม: O(1) — ผ่านข้อท้าของโจทย์
ข้อดี: เร็วและประหยัดสุด ใช้ได้ทุกภาษา
ข้อเสีย: ใช้ได้เฉพาะ “ซ้ำ 2 ครั้ง” ถ้าโจทย์เปลี่ยนเป็นซ้ำ 3 ครั้ง ต้องใช้เทคนิคอื่น และคนที่ไม่รู้จัก XOR อ่านแล้วงง ต้องมีคอมเมนต์

โค้ดทั้ง 4 วิธี พร้อมเทสต์

import unittest
from collections import Counter

def single_counter(nums):
    for x, c in Counter(nums).items():
        if c == 1:
            return x

def single_sort(nums):
    s = sorted(nums)
    for i in range(0, len(s) - 1, 2):
        if s[i] != s[i + 1]:
            return s[i]
    return s[-1]

def single_setmath(nums):
    return 2 * sum(set(nums)) - sum(nums)

def single_xor(nums):
    r = 0
    for x in nums:
        r ^= x  # คู่ที่ซ้ำหักล้างกันเป็น 0
    return r

ALL = [single_counter, single_sort, single_setmath, single_xor]

class SingleNumberTest(unittest.TestCase):
    def test_examples(self):
        for f in ALL:
            self.assertEqual(f([2, 2, 1]), 1, f.__name__)
            self.assertEqual(f([4, 1, 2, 1, 2]), 4, f.__name__)
            self.assertEqual(f([1]), 1, f.__name__)

    def test_negative_and_last_position(self):
        for f in ALL:
            self.assertEqual(f([-3, 7, 7]), -3, f.__name__)
            self.assertEqual(f([5, 5, 9, 9, 11]), 11, f.__name__)

if __name__ == "__main__":
    unittest.main()

Benchmark ที่รันจริง (17 ต.ค. 2026 บนเครื่องนี้)

วัดด้วย timeit บน Python 3.14.7 (x86_64) ลิสต์สุ่มยาว 100,001 ตัว (50,000 คู่ + ตัวโสด 1 ตัว สลับตำแหน่งแบบสุ่ม) วัด 5 รอบเอาค่าดีที่สุด

วิธี	เวลาต่อครั้ง (ms)	ที่เพิ่ม
แพนด้า: XOR	0.696	O(1)
กระต่าย: สูตรผลรวม	2.064	O(n)
ผึ้ง: Counter	2.348	O(n)
เป็ด: เรียงแล้วจับคู่	6.652	O(n) (sorted)

แพนด้าชนะทั้งเวลาและหน่วยความจำในการวัดครั้งนี้ เร็วกว่าเป็ดเกือบ 10 เท่า ส่วนกระต่ายกับผึ้งสูสีกัน ตัวเลขเป็นของเครื่องนี้เท่านั้น เครื่องคุณจะต่างไป

ตารางเลือกวิธีตามสถานการณ์

สถานการณ์	เลือก	เหตุผล
สัมภาษณ์ไวท์บอร์ด (โจทย์ท้า O(1) ที่)	แพนด้า (XOR)	ผ่านข้อท้า และอธิบายด้วยกฎ 2 ข้อได้
สัมภาษณ์ อยากเริ่มจากของที่ชัวร์	ผึ้ง แล้วต่อด้วยแพนด้า	แสดงว่าเข้าใจปัญหา แล้วค่อยลดหน่วยความจำ
โค้ดงานจริง ข้อมูลอาจไม่ตรงเงื่อนไข 100%	ผึ้ง (Counter)	ถ้ามีตัวซ้ำ 3 ครั้งหลุดมา ยังตรวจจับได้ ส่วน XOR จะให้คำตอบผิดเงียบๆ
Production hot path ที่รับประกันเงื่อนไขแล้ว	แพนด้า (XOR)	เร็วสุดและไม่จองหน่วยความจำ
สอนมือใหม่	เป็ด แล้วต่อด้วยผึ้ง	เห็นภาพการจับคู่ก่อน แล้วค่อยรู้จัก dict

ค่าเริ่มต้นภายใต้เงื่อนไขของโจทย์: XOR ครับ เพราะโจทย์รับประกันว่าทุกตัวอื่นซ้ำพอดี 2 ครั้ง

บารอนสรุป

บารอนบอกว่า “แพนด้าชนะเพราะโจทย์เขียนกติกาไว้ให้เขาชนะ” ถ้ากติกาเปลี่ยน ผึ้งที่จดทุกอย่างจะรอดกว่า ในงานจริงที่ข้อมูลมาจากผู้ใช้หรือไฟล์ข้างนอก ให้ถามก่อนว่าเงื่อนไข “ซ้ำ 2 ครั้งพอดี” รับประกันได้จริงไหม ถ้าไม่แน่ใจ ใช้ Counter แล้วเช็กว่ามีตัวที่นับได้ 1 อยู่ตัวเดียวจริง

Recap

จำกฎ XOR: a ^ a = 0 และ a ^ 0 = a ลำดับไม่สำคัญ
โจทย์ท้า O(1) ที่ → XOR (วัดได้ 0.696 ms ที่ 100,001 ตัวบนเครื่องนี้)
ข้อมูลไม่แน่ใจเงื่อนไข → Counter แล้วตรวจผล
ระวังสูตรผลรวมล้นในภาษาที่ int มีขนาดจำกัด
เขียนคอมเมนต์ข้างบรรทัด XOR ให้เพื่อนร่วมทีมอ่านออก
ลองดัดแปลงเป็น “ทุกตัวซ้ำ 3 ครั้ง” แล้วดูว่าวิธีไหนยังใช้ได้