Tìm phần tử chiếm đa số (Majority Element) trong mảng Python

Mô tả bài toán

Cho mảng số nguyên, tìm phần tử xuất hiện > n/2 lần (majority element).

Ví dụ:

• [1,2,4,3,3,1,1,5] (n=8) → 1 xuất hiện 3 lần, không > 4. Đề bài gốc có lỗi logic.
• [2,1,1,2,2,2] (n=6) → 2 xuất hiện 4 lần > 3 → Majority = 2.

Giải pháp 1: Hash map đếm tần suất (O(n) time, O(n) space)

def checkMajorityElement(arr, N):
    mp = {}
    for i in range(N):
        if arr[i] in mp:
            mp[arr[i]] += 1
        else:
            mp[arr[i]] = 1
    
    for key, count in mp.items():
        if count > N / 2:
            return key
    return -1

# Test
arr = [2,1,1,2,2,2]
N = len(arr)
ans = checkMajorityElement(arr, N)
if ans != -1:
    print(f"Majority Element: {ans}")
else:
    print("Không có majority element")

Giải pháp 2: Boyer-Moore Voting Algorithm (O(n) time, O(1) space - tối ưu)

def majorityElement(nums):
    """Boyer-Moore: tìm candidate, sau đó verify."""
    candidate = None
    count = 0
    
    # Phase 1: Tìm candidate
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    
    # Phase 2: Verify candidate
    if nums.count(candidate) > len(nums) // 2:
        return candidate
    return -1

# Test
print(majorityElement([2,1,1,2,2,2]))  # 2
print(majorityElement([1,2,3,4]))      # -1

Giải pháp 3: Dùng Counter (Pythonic)

from collections import Counter

def majority_element(arr):
    counts = Counter(arr)
    n = len(arr)
    for val, cnt in counts.items():
        if cnt > n // 2:
            return val
    return -1

Đầu ra

Majority Element is: 2

Lưu ý: Majority element bắt buộc xuất hiện > n/2 lần. Nếu đề bài chỉ hỏi "phần tử xuất hiện nhiều nhất" (mode), dùng Counter.most_common(1).