Tìm phần tử trong mảng đã sắp xếp có tần suất lớn hơn hoặc bằng n / 2 trong C ++.

Xét chúng ta có một mảng với kích thước n. Mảng này được sắp xếp. Có một phần tử có tần số lớn hơn hoặc bằng n / 2, với n là số phần tử trong mảng. Vì vậy, nếu mảng giống như [3, 4, 5, 5, 5], thì đầu ra sẽ là 5.

Nếu chúng ta quan sát kỹ loại mảng này, chúng ta có thể dễ dàng nhận thấy rằng số có tần số lớn hơn hoặc bằng n / 2, cũng sẽ xuất hiện ở chỉ số n / 2. Vì vậy, phần tử có thể được tìm thấy ở vị trí n / 2

Ví dụ

Source Code:
#include<iostream>
using namespace std;
int higherFreq(int arr[], int n) {
   return arr[n / 2];
}
int main() {
   int arr[] = { 1, 2, 3, 4 , 4, 4, 4, 4, 4, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "The number " << higherFreq(arr, n) << " has occurred more than or equal to "<<n <<"/2 amount of times";
}

Đầu ra -

The number 4 has occurred more than or equal to 10/2 amount of times