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

浏览数：22 / 时间：2015年06月11日

http://www.geeksforgeeks.org/given-an-array-of-of-size-n-finds-all-the-elements-that-appear-more-than-nk-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 }

 

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

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： Android iOS 移动互联 终端开发

相关文章

随机文章

您可能还喜欢

您可能还喜欢