Tìm ra phần tử phổ biến nhất

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Đề bài:

Cho 1 mảng gồm n phần tử, trả về phần tử xuất hiện hơn (n/2) lần, cho rằng phần tử đó luôn tồn tại.

cách 1: Sort table

Hướng tiếp cận:

• Đơn giản thôi, chúng ta sẽ sort mảng đã cho và trả về phần tử ở vị trí n/2

Time complexity: O(n)

Space complexity: O(1)

Code

def majorityElement(self, nums: List[int]):
    nums.sort()
    return nums[len(nums) // 2]

Cách 2: hashmap ( or hashtable)

Hướng tiếp cận:

Chúng ta sẽ sử dụng 1 hash map để chứa đựng frequency của các phần tử trong nums. Sau đó duyệt qua hash map và trả về phần tử xuất hiện nhiều nhất trong mảng.

time complexity: O(n)

Space complexity: O(n)

Code

def majorityElement(self, nums: List[int]) -> int:
    nums_frequency = {}
    for ele in nums:
      nums_frequency[ele] = nums_frequency.get(ele, 0) + 1
    
    for key,value in nums_frequency.items():
      if value > len(nums)/2:
        return key
      
    return 0

Cách 3: Moore voting algorithm

Hướng tiếp cận:

Chúng ta có thể nhìn nhập rằng, nếu phần từ xuất hiện hơn n/2 lần thì khi lấy tổng số frequency của phần tử này trừ đi cho các phần tử còn lại. chúng ta luôn được số nguyên dương.

Time complexity: O(n)

Space complexity: O(1)

Code

def majorityElement(self, nums: List[int]) -> int:
    candidate  = 0
    count = 0
    for num in nums:
      if count == 0:
        candidate = num
      
      if num == candidate:
        count += 1
      else:
        count -= 1
    
    return candidate

Test

input

[3,2,3]

Output

3

Input

[5]

Output

5

Input

[8,8,3,5,8]

Output

8

Ref: https://leetcode.com/problems/majority-element/description/