Kiểm tra phần tử chiếm ưu thế trong mảng đã sắp xếp trong C++

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

Cách làm: đếm tần suất x trong mảng (dừng sớm khi gặp phần tử > x nhờ mảng đã sắp xếp), so sánh với n/2.

Ví dụ

#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;
    }
    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