时间戳

首页 > 技术文章 > 电话聊天狂人

电话聊天狂人

onlyblues 2021-05-28 20:06 原文

电话聊天狂人

给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。

输入格式:

输入首先给出正整数N（≤ 105），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。

输出格式:

在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。

输入样例:

4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832

输出样例:

13588625832 3

 

解题思路

　　散列表的应用。

　　先给出手写实现哈希散列的AC代码，这里用的是搭配std::vector的分离链接法：

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <vector>
  6 #include <algorithm>
  7 
  8 const int MAXN = 11;
  9 
 10 struct Node {
 11     char telNum[MAXN + 1];
 12     int cnt;
 13 };
 14 
 15 struct HashTable {
 16     std::vector<std::vector<Node> > head;
 17     int tableSize;
 18 };
 19 
 20 int nextPrime(int n);
 21 HashTable *createTable(int n);
 22 bool operator==(Node &a, char *key);
 23 void insert(char *key, HashTable *ht);
 24 void scanAndOutput(HashTable *ht);
 25 
 26 int main() {
 27     int n;
 28     scanf("%d", &n);
 29     HashTable *ht = createTable(n);
 30     
 31     for (int i = 0; i < 2 * n; i++) {
 32         char telNum[MAXN];
 33         scanf("%s", telNum);
 34         insert(telNum, ht);
 35     }
 36     
 37     scanAndOutput(ht);
 38     
 39     return 0;
 40 }
 41 
 42 int nextPrime(int n) {
 43     int i = n % 2 ? n + 2 : n + 1;
 44     while (true) {
 45         int j = (int)sqrt(i);
 46         for ( ; j > 2; j--) {
 47             if (i % j == 0) break;
 48         }
 49         if (j == 2) break;
 50         i += 2;
 51     }
 52     
 53     return i;
 54 }
 55 
 56 HashTable *createTable(int n) {
 57     HashTable *ht = new HashTable;
 58     ht->tableSize = nextPrime(n);
 59     ht->head.resize(ht->tableSize);
 60     
 61     return ht;
 62 }
 63 
 64 bool operator==(Node &a, char *key) {
 65     return strcmp(a.telNum, key) == 0;
 66 }
 67 
 68 void insert(char *key, HashTable *ht) {
 69     int pos = atoi(key + MAXN - 5) % ht->tableSize;
 70     std::vector<Node>::iterator it = find(ht->head[pos].begin(), ht->head[pos].end(), key);
 71     if (it == ht->head[pos].end()) {
 72         Node tmp;
 73         strcpy(tmp.telNum, key);
 74         tmp.cnt = 1;
 75         ht->head[pos].push_back(tmp);
 76     }
 77     else {
 78         it->cnt++;
 79     }
 80 }
 81 
 82 void scanAndOutput(HashTable *ht) {
 83     int max = 0, cnt = 0;
 84     char *minTel;
 85     for (int i = 0; i < ht->tableSize; i++) {
 86         for (std::vector<Node>::iterator it = ht->head[i].begin(); it != ht->head[i].end(); it++) {
 87             if (it->cnt > max) {
 88                 max = it->cnt;
 89                 minTel = it->telNum;
 90                 cnt = 1;
 91             }
 92             else if (it->cnt == max) {
 93                 cnt++;
 94                 if (strcmp(it->telNum, minTel) < 0) minTel = it->telNum;
 95             }
 96         }
 97     }
 98     
 99     printf("%s %d", minTel, max);
100     if (cnt > 1) printf(" %d", cnt);
101 }

　　然后是用std::unordered_map实现的散列，使用STL代码就简短许多了，思路其实还是一样的。

 1 #include <iostream>
 2 #include <string>
 3 #include <unordered_map>
 4 using namespace std;
 5 
 6 int main() {
 7     int n;
 8     scanf("%d", &n);
 9     unordered_map<string, int> mp;
10     for (int i = 0; i < 2 * n; i++) {
11         string tel;
12         cin >> tel;
13         ++mp[tel];
14     }
15     
16     int maxN = 0, cnt = 0;
17     string minTel;
18     for (auto &it : mp) {
19         if (it.second > maxN) {
20             maxN = it.second;
21             cnt = 1;
22             minTel = it.first;
23         }
24         else if (it.second == maxN) {
25             if (it.first < minTel) minTel = it.first;
26             cnt++;
27         }
28     }
29     
30     cout << minTel << ' ' << maxN;
31     if (cnt > 1) cout << ' ' << cnt;
32     
33     return 0;
34 }

　　最后给出一种很巧妙的解法。就是把这些电话号码输入存放到数组中，然后进行排序，遍历一遍数组，找到次数最多的那个号码。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 bool cmp(const string &a, const string &b) {
 7     return a < b;
 8 }
 9 
10 int main() {
11     int n;
12     cin >> n;
13     string a[2 * n];
14     for (int i = 0; i < 2 * n; i++) {
15         cin >> a[i];
16     }
17     sort(a, a + 2 * n, cmp);
18     
19     int max = 0, cnt = 1, same = 1, beg = 0;
20     string str;
21     for (int k = 1; k < 2 * n; k++) {
22         if (a[beg] == a[k]) {
23             cnt++;
24         }
25         else {
26             cnt = 1;
27             beg = k;
28         }
29         if (cnt > max) {
30             max = cnt;
31             same = 1;
32             str = a[beg];
33         }
34         else if (cnt == max) {
35             same++;
36         }
37     }
38     cout << str << ' ' << max;
39     if (same > 1) cout << ' ' << same;
40     
41     return 0;
42 }

 

参考资料

　　浙江大学——数据结构：https://www.icourse163.org/course/ZJU-93001?tid=1461682474

推荐阅读