𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁

𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁

Leetcode 169 ให้คุณหา majority element ใน array โดยที่ majority element จะปรากฏขึ้นมากกว่า n / 2 ครั้ง และเราสมมติว่ามันมีอยู่เสมอ

คุณสามารถแก้ปัญหานี้ได้สองวิธี

วิธีที่ 1: การใช้ Map (The Map Method)

วิธีนี้ใช้ Map เพื่อบันทึกจำนวนครั้งที่ตัวเลขแต่ละตัวปรากฏขึ้น

• สร้าง Map เพื่อเก็บจำนวนนับ
• วนลูปผ่าน array
• อัปเดตจำนวนนับสำหรับตัวเลขแต่ละตัว
• วนลูปผ่าน Map เพื่อหาตัวเลขที่มีจำนวนนับมากกว่า n / 2

ความซับซ้อน (Complexity):

• เวลา (Time): O(n) เนื่องจากมีการใช้ลูปสองชุดเรียงต่อกัน
• พื้นที่ (Space): O(n) เนื่องจากขนาดของ Map จะเพิ่มขึ้นตามจำนวนสมาชิกที่ไม่ซ้ำกัน

วิธีที่ 2: Boyer-Moore Voting Algorithm

นี่คือวิธีที่ปรับปรุงให้มีประสิทธิภาพมากขึ้น (optimized) โดยใช้หน่วยความจำคงที่ (constant memory)

ลองนึกภาพว่าตัวเลขแต่ละตัวคือทีมที่อยู่ฝ่ายตรงข้ามกัน ทุกครั้งที่ตัวเลขหนึ่งพบกับตัวเลขอื่นที่ไม่เหมือนกัน พวกมันจะหักล้างกันไป และเนื่องจาก majority element ปรากฏขึ้นมากกว่าครึ่งหนึ่งของทั้งหมด มันจึงจะเป็นตัวสุดท้ายที่ยังคงเหลืออยู่เสมอ

หลักการทำงาน:

• เลือกตัวเลขที่เป็นผู้สมัคร (candidate) และตั้งค่าจำนวนนับ (count) เป็น 0
• วนลูปผ่าน array
• ถ้าจำนวนนับเป็น 0 ให้ตั้งค่าตัวเลขปัจจุบันเป็นผู้สมัคร
• ถ้าตัวเลขปัจจุบันตรงกับผู้สมัคร ให้เพิ่มจำนวนนับขึ้น 1
• ถ้าไม่ตรงกัน ให้ลดจำนวนนับลง 1

ความซับซ้อน (Complexity):

• เวลา (Time): O(n) เนื่องจากคุณวนลูปผ่าน array เพียงรอบเดียว
• พื้นที่ (Space): O(1) เนื่องจากคุณใช้เพียงตัวแปรสองตัวเท่านั้น

ทำไมเรื่องนี้ถึงสำคัญ:

ทั้งสองวิธีมีความซับซ้อนด้านเวลา (time complexity) อยู่ที่ O(n) อย่างไรก็ตาม วิธีที่สองใช้หน่วยความจำน้อยกว่ามาก เนื่องจากไม่จำเป็นต้องใช้ Map ซึ่งทำให้เหมาะสำหรับชุดข้อมูลขนาดใหญ่

ที่มา: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6