C ++のソートされた配列で25％を超えて表示される要素

配列Aがあるとします。要素はほとんどありません。いくつかの要素は一般的です。配列に25％以上のスペースが表示されている要素を返す必要があります。したがって、A =[1、2、4、4、4、4、5、5、6、6、7、7]の場合、ここで4が4回発生しています。これは12（アレイのサイズ）の25％以上です

これを解決するには、次の手順に従います-

• 要素を読み取り、それぞれの頻度を保存します
• 頻度が配列サイズの25％を超える場合は、結果を返します。

例

理解を深めるために、次の実装を見てみましょう-

#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);
}

入力

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

出力

4