Phần tử chiếm ưu thế (Majority Element) trong C++

Cho mảng đã sắp xếp, kiểm tra số x có phải phần tử chiếm ưu thế hay không. Phần tử chiếm ưu thế: xuất hiện > n/2 lần. Ví dụ: {1, 2, 3, 3, 3, 3, 6}, x=3 → true (4 lần > 7/2).

Giải pháp

Đếm tần suất x trong mảng (dừng sớm khi gặp phần tử > x vì mảng đã sắp xếp). So sánh với n/2.

Chương trình C++

#include <iostream> 
#include <stack> 
using namespace std; 

bool isMajorityElement(int arr[], int n, int x) {
    int freq = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) freq++;
        if (arr[i] > x) break;  // Tối ưu: mảng đã sắp xếp
    }
    return (freq > n / 2);
}

int main() {
    int arr[] = {1, 2, 3, 3, 3, 3, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    if (isMajorityElement(arr, n, x))
        cout << x << " is the majority element of the array";
    else
        cout << x << " is not the majority element of the array";
}

Kết quả

3 is the majority element of the array

Lưu ý

Với mảng chưa sắp xếp, có thể dùng thuật toán Boyer-Moore Voting Algorithm O(n) thời gian, O(1) không gian.