Majority Element

TODO: update inscribed. TODO: rewrite the entire article

Understand Problem

โจทย์กำหนดให้เราหาเลขที่มีจำนวนใน array เยอะที่สุด โดยที่ตัวเลขนั้นต้องมีจำนวนมากกว่า \(\frac{n}{2}\) โดย \(n\) คือจำนวน item ใน array

Solution #1: Naive Solution

นับตัวเลขทั้งหมดใน array โดยหลักจากการนับเสร็จเรียบร้อยให้ดูว่าค่าตัวเลขไหนมีค่าเยอะที่สุดและคืนค่าตัวนั้นออกมา

โดยจาก case ตังอย่างที่ยกมาจะเห็นได้ว่า การแก้ปัญหาด้วยวิธีนี้จะต้องทำการ loop อย่างน้อย 2 ครั้งคือ ครั้งแรกกับการนับจำนวนตัวเลข และครั้งที่สองสำหรับการหาตัวเลขที่มีจำนวนมากกว่า n/2 โดยถ้าเราคิด Big(O) Time complexity จะเท่ากับ O(2n) ซึ่งจะอยู่ใน class O(n) และ space conplexity จะอยู่ที่ O(n) นั่นเอง

ไอเดียการแก้ปัญหาที่ 2 (ลองทำให้มันเร็วขึ้นได้ไหม ?)

จากไอเดียแรกจะเห็นได้ว่าการ loop ทั้ง 2 ครั้ง นั้นทำให้เราเสียเวลาอย่างมาก คำถามที่เกิดขึ้นคือ

จะเป็นได้ได้ไหมที่จะลดการ loop ให้น้อยลง ?

ลองเช็กค่าตั้งแต่ต้องเรานับ

โดยในวิธีการนี้จะทำการเช็กว่าตัวเลขนั้นมีจำนวนเกิน n/2 แล้วหรือยังถ้าเกินก็จะให้คืนค่าออกไปเลยโดยที่ไม่ต้องทำอย่างอื่นต่อเพราะในโจทย์นี้กำหนดให้จะมีตัวเลขที่มีจำนวนมากกว่า n/2 เสมอ

1
class Solution:
2
    def majorityElement(self, nums: List[int]) -> int:
3
        nums_target = len(nums)/2
4
        count_num = {}
5
        for num in nums:
6
            if num in count_num.keys():
7
                count_num[num] += 1
8
                if count_num[i] > nums_target:
9
                  return i
10
            else:
11
                count_num[num] = 1

ผลลัพธ์

TODO: add image

จะเห็นได้ว่าวิธีการนี้เป็นวิธีการที่ผิดเพราะเรายังไม่ได้คำนึงถึง case ที่ array มี length แค่ 1 ทำให้ function ของ เรา return ค่า null ใน case ที่ length = 1 นั่นเอง โดยการแก้ไขปัญหานี้คือ

1. สร้าง if condition มาดักตั้งแต่แรก

1
class Solution:
2
    def majorityElement(self, nums: List[int]) -> int:
3
        if len(nums) == 1:
4
            return nums[0]
5
        else:
6
            nums_target = len(nums)/2
7
            count_num = {}
8
            for num in nums:
9
                if num in count_num.keys():
10
                    count_num[num] += 1
11
                    if count_num[num] > nums_target:
12
                        return num
13
                else:
14
                    count_num[num] = 1

return หลังออกจาก loop

1
class Solution:
2
    def majorityElement(self, nums: List[int]) -> int:
3
        nums_target = len(nums)/2
4
        count_num = {}
5
        for num in nums:
6
            if num in count_num.keys():
7
                count_num[num] += 1
8
                if count_num[num] > nums_target:
9
                    return num
10
            else:
11
                count_num[num] = 1
12
        return nums[0]

ที่นี้เราก็ลดการทำงาน เหลือ loop เดียวได้แล้วทำให้ Big(O) ปัจจุบันอยู่ที่ O(n) แต่ space conplexity ยังไม่ได้ลดลงจากวิธีแรก

ไอเดียการแก้ปัญหาที่ 3 (Could you solve the problem in linear time and in O(1) space?)

โดยจากโจทย์ให้ hint เล็ก ๆ ว่า สามารถแก้ปัญหานี้ด้วย linear time O(n) (โดยปัจจุบันเราทำได้แล้ว) และ O(1) Space (โดยวิธีการปัจจุบันคือ O(n) space)

แล้วเราจะทำยังไงให้ใช้ Space ลดลง ?

โดยถ้าเราจะใช้พื้นที่ลดลงนั้นหมายถึงการสร้างตัวแปลที่ไว้เก็บค่าแค่ตัวเดียวหรือแก้ไข้ค่าที่มีอยู่แล้ว (nums array)

วิธีที่ 1 Sort ก่อนและแสดงค่าที่ floor(n/2)

โดยวิธีการนี้จะทำการ sort array และ เรียกค่าที่ตำแหน่ง n/2 ออกมาเพราะจากโจทย์บอกว่า array จะมีค่า majority เสมอ (majority element always exists in the array) ทำให้เมื่อ sort แล้วก็จะได้ค่าที่มากที่สุดอยู่ตรงกลางเสมอนั่นเอง

TODO: just image

1
class Solution:
2
    def majorityElement(self, nums: list[int]) -> int:
3

4
        nums.sort()
5
        return nums[len(nums) // 2]

รู้หรือไม่ .sort() ไม่ได้ใช้ Time Complexity O(1) แต่ใช้ O(nLog(n)) เพราะค่าเริ่มต้นของ .sort() จะเป็น Algolithm quick sort ซึ่งจะมี Time Complexity เป็น O(nLog(n)) นั่นเอง

จะเห็นได้ว่าเราสามารถลด Space Complexity เหลือ O(1) ได้แล้วแต่ Time Complexity ของเราเพิ่มเป็น O(nLog(n)) แทน

วิธีที่ 2 Boyer-Moore algorithm

โดยหลัการของ Boyer-Moore algorithm คือจะทำการ track candidate และ count (ค่าความน่าจะเป็นที่ candidate จะเป็น majority**) แลัวเมื่อ count = 0 จำทำการเปลี่ยน candidate นั่นเอง โดยมีเงื่อนไขคือ** array จะมีค่า majority เสมอ

1
class Solution:
2
  def majorityElement(nums):
3
      count = 0
4
      candidate = None
5

6
      for num in nums:
7
          if count == 0:
8
              candidate = num
9
          count += (1 if num == candidate else -1)
10

11
      return candidate

TODO: try to explain this myself

แล้วทำไมวิธีการนี้ถึงสามารถการันตีว่าจะสามารถหาค่าที่เป็น mijority ได้เสมอ ก็เพราะใน algorithm นี้ จะทำงานอยู่ 2 ขั้นตอนหลัก ๆ คือ การ update ค่า count และ การเช็ก candidate โดยในขั้นตอนแรกถ้าค่าที่ pointer อยู่ ณ ปัจจุบัน คือด้วยเดียวกับ candidate ปัจจุบัน ให้บวก +1 ที่ค่า count ถ้าไม่ใช่ให้ทำการ -1 แทน ต่อมาการเช็ก candidate เมื่อ count มีค่า เท่ากับ 0 ก็จะ update ค่า candidate ให้เท่ากับค่าใน index ปัจจุบันนั่นเอง จะเห็นได้ว่าถ้าเลขใน array ของเราเป็น mijority (count(x) ≥ n/2) และเราจะสามารถสมมุติภาพให้เลขที่เป็น mijority ของเรามาเรียงกันอยู่หน้าสุดทุกตัวทำให้ในกรณีนี้ count จะมีค่าอย่างน้อย n/2 ทำให้เมื่อไปเจอค่าที่เหลือใน array count ก็จะไม่สามารถ เหลือ 0 หรือติดลบได้นั่นเอง และในกรณีที่เลข mijority ของเราไม่ได้อยู่เรียงกัน count ก็ยังจะเป็นค่าที่มาที่สุดอยู่ดีถึงแม้ว่า count จะเป็น 0 และถูกเปลี่ยนไปยังไง ค่า mijority ของเรา ก็จะเปลี่ยนกลับมาได้เสมอ

และสุดท้ายจะเห็นว่า Algorithm นี้จะมี Time Complexity ที่ O(n) และ Space Complexity ที่ O(1) เป็นไปตามที่โจทย์ได้บอกว่า “Could you solve the problem in linear time and in O(1) space?” นั่นเอง