คำอธิบายปัญหา
สมมติว่าเรามีอาร์เรย์ เราต้องตรวจสอบว่าตัวเลข x ที่กำหนดเป็น Majority Element ของอาร์เรย์นั้นหรือไม่ อาร์เรย์ถูกเรียงลำดับแล้ว องค์ประกอบหนึ่งถูกกล่าวว่าเป็น Majority Element เมื่อมันปรากฏ n/2 ครั้งในอาร์เรย์ สมมติอาร์เรย์เป็น {1, 2, 3, 3, 3, 3, 6}, x = 3 คำตอบคือ true เพราะ 3 เป็น Majority Element ของอาร์เรย์ มี 3 อยู่ 4 ตัว ขนาดอาร์เรย์คือ 7 ดังนั้น 4 > 7/2
เราสามารถนับจำนวนครั้งที่ x ปรากฏในอาร์เรย์ และถ้าจำนวนมากกว่า 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"; }นำเข้า
[1, 2, 3, 3, 3, 3, 6] 3
ผลลัพธ์
3 is the majority element of the array
