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

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

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

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.
source: viblo