Data Structure Array: Given an array of of size n and a number k, find all elements that appear more than n/k times

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <stack>
 6 #include <string>
 7 #include <fstream>
 8 #include <map>
 9 using namespace std;
10 
11 void more(int arr[], int n, int k) {
12     map<int, int> S;
13     for (int i = 0; i < n; i++) {
14         if (S.find(arr[i]) != S.end()) S[arr[i]]++;
15         else if (S.size() == k) {
16             for (map<int, int>::iterator it = S.begin(); it != S.end(); it++) {
17                 if (it->second == 1) S.erase(it->first);
18                 else it->second--;
19             }
20         }
21         else S[arr[i]] = 1;
22     }
23     for (map<int, int>::iterator it = S.begin(); it != S.end(); it++) {
24         int tmp = 0;
25         for (int i = 0; i < n; i++) {
26             if (arr[i] == it->first) tmp++;
27         }
28         if (tmp > n / k) cout << it->first << " ";
29     }
30 }
31 
32 int main() {
33     int arr[7] = {4, 5, 6, 7, 8, 4, 4};
34     more(arr, 7, 3);
35     return 0;
36 }