衆數問題
時間限制:3000 ms | 記憶體限制:65535 KB
難度:3
- 描述
-
所謂衆數,就是對于給定的含有N個元素的多重集合,每個元素在S中出現次數最多的成為該元素的重數,
多重集合S重的重數最大的元素成為衆數。例如:S={1,2,2,2,3,5},則多重集S的衆數是2,其重數為3。
現在你的任務是:對于給定的由m個自然數組成的多重集S,計算出S的衆數及其重數。
- 輸入
-
第一行為n,表示測試資料組數。(n<30)
每組測試的第一行是一個整數m,表示多重集S中元素的個數為m
接下來的一行中給出m(m<100)個不大于10萬的自然數
(不會出現不同元素出現的次數相同的情況,如:S={11,11,22,22,33,33})。
- 輸出
- 每組測試資料輸出一行,包含兩個數,第一個是衆數,第二個是其重數,中間以空格隔開。
- 樣例輸入
-
1 6 1 2 2 2 3 5
- 樣例輸出
-
2 3 用hash表;
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 int hash[100010]; 6 7 int main(){ 8 int n, m, temp; 9 cin >> n; 10 while(n--){ 11 memset(hash, 0, sizeof(hash)); 12 cin >> m; 13 for(int i = 0; i < m; i++){ 14 cin >> temp; 15 hash[temp]++; 16 } 17 int max = 0, mark; 18 for(int i = 0; i < 100001; i++){ 19 if(hash[i] > max){ 20 max = hash[i]; 21 mark = i; 22 } 23 } 24 printf("%d %d\n", mark, max); 25 } 26 return 0; 27 }
1 2 #pragma warning(disable:4786) 3 #include <iostream> 4 #include <cstdio> 5 #include <set> 6 using namespace std; 7 8 int main(){ 9 multiset<int> ms; 10 int n, m, temp; 11 cin >> n; 12 while(n--){ 13 ms.clear(); 14 cin >> m; 15 for(int i = 0; i < m; i++){ 16 cin >> temp; 17 ms.insert(temp); 18 } 19 multiset<int>::iterator it = ms.begin(); 20 int max = ms.count(*it); 21 int num = *it; 22 it++; 23 while(it != ms.end()){ 24 if(ms.count(*it) > max){ 25 max = ms.count(*it); 26 num = *it; 27 } 28 it++; 29 } 30 cout << num << " " << max << endl; 31 } 32 return 0; 33 }
越努力,越幸運