LeetCode #169 Majority Element: นับ จัดเรียง หรือหักคะแนนเสียง

Majority Element #169 ถามค่าที่ปรากฏ มากกว่าครึ่ง ของจำนวนสมาชิกทั้งหมด ไม่ใช่แค่ค่าที่พบบ่อยที่สุดครับ เช่น [2, 2, 1, 1, 1, 2, 2] ตอบ 2 เพราะเจอสี่ครั้งจากเจ็ดครั้ง โจทย์รับประกันว่ามี majority เสมอ ความรับประกันนี้สำคัญต่อวิธีใช้ memory คงที่

มีสมาชิก 1 ถึง 50,000 ค่า และค่าอาจติดลบ เราเทียบสามแนวคิดที่ตรวจคำตอบได้เหมือนกัน แต่ต่างกันด้าน memory, ความอ่านง่าย และความเหมาะกับ stream

วิธี 1: นับด้วย dictionary

นับทุกค่าหนึ่งรอบแล้วหาค่าที่มากกว่า n//2 เวลา O(n) และพื้นที่ O(u) เมื่อ u คือจำนวนค่าต่างกัน อ่านตรงกับโจทย์ที่สุด และยังใช้ได้เมื่อโจทย์เปลี่ยนให้ถามจำนวนหรือให้ตรวจว่า majority มีจริงหรือไม่

วิธี 2: sort แล้วหยิบค่ากลาง

ถ้ามีค่าหนึ่งเกินครึ่ง เมื่อเรียงแล้วตำแหน่งกลางต้องเป็นค่านั้น ใช้ sorted(nums) เพื่อไม่แก้ input เวลา O(n log n) และพื้นที่ O(n) ในตัวอย่าง Python แต่ถ้า input เรียงอยู่แล้ว วิธีนี้เป็นการอ่านตำแหน่งกลาง O(1) ทันที

วิธี 3: Boyer–Moore voting

จับคู่ค่าที่ต่างกันแล้วตัดกันทีละคู่ ถ้ามีเสียงมากกว่าครึ่ง เสียงนั้นจะเหลือเป็น candidate แน่ เดิน array รอบเดียว เวลา O(n) พื้นที่เพิ่ม O(1) และทำแบบ streaming ได้ นี่คือ best default ภายใต้ guarantee ของโจทย์ หากใช้กับข้อมูลจริงที่อาจไม่มี majority ต้องเดินอีกรอบนับ candidate ก่อนคืน

from collections import Counter
import unittest


def majority_count(nums: list[int]) -> int:
    counts = Counter(nums)
    return next(value for value, count in counts.items() if count > len(nums) // 2)


def majority_sort(nums: list[int]) -> int:
    return sorted(nums)[len(nums) // 2]


def majority_vote(nums: list[int]) -> int:
    candidate = None
    balance = 0
    for value in nums:
        if balance == 0:
            candidate = value
        balance += 1 if value == candidate else -1
    assert candidate is not None
    return candidate


class MajorityTests(unittest.TestCase):
    def test_all_methods(self):
        cases = [([3], 3), ([3, 2, 3], 3),
                 ([2, 2, 1, 1, 1, 2, 2], 2), ([-1, -1, 5], -1)]
        for solve in (majority_count, majority_sort, majority_vote):
            for values, expected in cases:
                with self.subTest(solve=solve.__name__, values=values):
                    self.assertEqual(solve(values), expected)


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

Decision table

สถานการณ์	นับ	Sort copy	Vote
Input เล็กและเน้นอ่านง่าย	ตรงที่สุด	ง่าย	ต้องอธิบาย invariant
Memory จำกัด	O(u)	O(n)	O(1)
Stream ทีละค่า	เก็บ counters	ต้องมีข้อมูลครบ	ทำได้ทันที
Input เรียงแล้ว	ยังนับ	อ่านกลาง O(1)	เดินหนึ่งรอบ
ห้ามแก้ input	ทำได้	ใช้ sorted copy	ทำได้
ไม่มี guarantee ว่ามี majority	ตรวจจาก count	ต้องนับซ้ำ	ต้องนับ candidate ซ้ำ

Edge cases

ค่าเดียวเป็น majority เสมอ ตัวเลขติดลบไม่ต่างจากบวก และค่า n/2 พอดี ยังไม่ใช่ majority การหักคะแนนของ Boyer–Moore ไม่ได้ให้จำนวนจริงของ candidate; มันให้ผู้ชนะภายใต้ guarantee เท่านั้น หากรับ input ภายนอกที่ไม่รับประกัน ให้ตรวจ nums.count(candidate) > len(nums)//2 ก่อนใช้ผลครับ

Recap

• แยก “มากที่สุด” ออกจาก “มากกว่าครึ่ง”
• นับอ่านง่ายและตรวจ guarantee ได้ตรง
• Vote เป็น default ในโจทย์นี้เมื่ออยากได้เวลา O(n) พื้นที่ O(1)
• ข้อมูลจริงที่ไม่มี guarantee ต้องตรวจ candidate รอบสอง