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/