Tìm Kiếm Phần Tử Xuất Hiện Thường Xuyên Nhất
Phần tử xuất hiện thường xuyên (majority element) là phần tử mà xuất hiện nhiều hơn ⌊n / 2⌋ lần trong mảng. Bài viết này sẽ hướng dẫn bạn ba phương pháp khác nhau để xác định phần tử này trong một mảng các số nguyên.
Đề Bài
Cho một mảng gồm n phần tử, hãy trả về phần tử xuất hiện hơn (n/2) lần. Chúng ta giả định rằng phần tử phần lớn luôn tồn tại trong mảng.
Phương Pháp 1: Sử Dụng Sắp Xếp Mảng
Hướng Tiếp Cận
Phương pháp này đơn giản và dễ hiểu. Chúng ta sẽ sắp xếp mảng đã cho và trả về phần tử ở vị trí n/2.
Độ Phức Tạp Thời Gian: O(n log n)
Độ Phức Tạp Không Gian: O(1)
Mã Nguồn
python
def majorityElement(self, nums: List[int]):
nums.sort()
return nums[len(nums) // 2]
Phương Pháp 2: Sử Dụng HashMap (hoặc Hashtable)
Hướng Tiếp Cận
Chúng ta sẽ sử dụng một hash map để lưu trữ tần suất (frequency) của các phần tử trong mảng nums. Tiếp theo, chúng ta sẽ duyệt qua hash map và trả về phần tử xuất hiện nhiều nhất.
Độ Phức Tạp Thời Gian: O(n)
Độ Phức Tạp Không Gian: O(n)
Mã Nguồn
python
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
Phương Pháp 3: Thuật Toán Bỏ Phiếu Moore
Hướng Tiếp Cận
Thuật toán này hoạt động dựa trên nguyên tắc rằng nếu một phần tử xuất hiện nhiều hơn n/2 lần, thì tổng tần suất của phần tử này trừ đi cho các phần tử còn lại sẽ luôn là một số nguyên dương.
Độ Phức Tạp Thời Gian: O(n)
Độ Phức Tạp Không Gian: O(1)
Mã Nguồn
python
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
Ví Dụ Kiểm Tra
Input
[3,2,3]
Output
3
Input
[5]
Output
5
Input
[8,8,3,5,8]
Output
8
Bài viết này dựa trên LeetCode và hy vọng sẽ giúp bạn hiểu rõ hơn về cách xác định phần tử xuất hiện thường xuyên nhất trong một mảng.