배열이 있다고 가정합니다. 주어진 숫자 x가 해당 배열의 다수 요소인지 여부를 확인해야 합니다. 배열이 정렬됩니다. 하나의 요소가 배열에서 n/2번 나타날 때 다수 요소라고 합니다. 배열이 {1, 2, 3, 3, 3, 3, 6}, x =3과 같다고 가정합니다. 여기서 3은 배열의 다수 요소이므로 대답은 참입니다. 4개의 3이 있습니다. 배열의 크기는 7이므로 4> 7/2를 볼 수 있습니다.
배열에서 x의 발생 횟수를 셀 수 있으며, 숫자가 n/2보다 크면 대답은 참이고 그렇지 않으면 거짓입니다.
예시(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