Phần tử xuất hiện nhiều hơn 25% trong mảng đã sắp xếp trong C ++

Giả sử chúng ta có một mảng A. Có ít phần tử. Một số yếu tố là chung. Chúng ta phải trả về một phần tử đang xuất hiện nhiều hơn 25% khoảng trắng trong mảng. Vì vậy, nếu A =[1, 2, 4, 4, 4, 4, 5, 5, 6, 6, 7, 7], ở đây 4 đã xảy ra bốn lần. Đây là hơn 25% của 12 (kích thước của mảng)

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Đọc các phần tử và lưu trữ tần số tương ứng của chúng
• Nếu tần suất lớn hơn 25% kích thước mảng thì trả về kết quả.

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
      int findSpecialInteger(vector<int>& arr) {
         int n = arr.size();
         int req = n / 4;
         unordered_map <int, int> m;
         int ans = -1;
         for(int i = 0; i < n; i++){
            m[arr[i]]++;
            if(m[arr[i]] > req)ans = arr[i];
         }
         return ans;
      }
};
main(){
   Solution ob;
   vector<int> c = {1,2,4,4,4,4,5,5,6,6,7,7};
   cout << ob.findSpecialInteger(c);
}

Đầu vào

[1,2,4,4,4,4,5,5,6,6,7,7]

Đầu ra

4