ตรวจสอบ Majority Element ใน Sorted Array ใน C++

สมมติมี Array ที่เรียงแล้ว ต้องการตรวจสอบว่า Number x เป็น Majority Element หรือไม่ Majority Element คือ Element ที่ปรากฏมากกว่า n/2 ครั้ง ตัวอย่าง Array {1, 2, 3, 3, 3, 3, 6}, x = 3 คำตอบ true เพราะ 3 ปรากฏ 4 ครั้ง n=7 ดังนั้น 4 > 7/2

นับ Frequency ของ x ใน Array ถ้ามากกว่า n/2 คืนค่า true มิฉะนั้น false

ตัวอย่างโค้ด 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;
    }
    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";
}

ผลลัพธ์

3 is the majority element of the array