Computer >> Máy Tính >  >> Lập trình >> C ++

Phần tử đa số trong C ++


Giả sử chúng ta có một mảng; chúng ta phải kiểm tra xem số x đã cho có phải là phần tử chính của mảng đó hay không. Mảng được sắp xếp. Một phần tử được cho là phần tử đa số khi nó xuất hiện n / 2 lần trong mảng. Giả sử một mảng giống như {1, 2, 3, 3, 3, 3, 6}, x =3, ở đây câu trả lời là đúng vì 3 là phần tử chính của mảng. Có bốn số 3. Kích thước của mảng là 7, vì vậy chúng ta có thể thấy 4> 7/2.

Chúng ta có thể đếm số lần xuất hiện của x trong mảng và nếu số lớn hơn n / 2, câu trả lời sẽ là true, ngược lại là false.

Ví dụ (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";
}

Đầu vào

[1, 2, 3, 3, 3, 3, 6]
3

Đầu ra

3 is the majority element of the array