题目描述

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

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

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

输入样例:
4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832
输出样例:
13588625832 3

思路

  • 建立一个哈希表，散列函数和冲突处理方法使用最简单的除留余数法和线性探测法
  • 每个号码在哈希表中都有一个位置，该位置保存了通话次数和号码
  • 遍历哈希表，找出通话次数最多的号码及其通话次数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<math.h>
using namespace std;
#define MAXTABLESIZE 100000 //散列表最大长度
typedef long long ElementType; //关键词类型
typedef int Position; //散列地址类型

typedef enum {Legitimate,Empty,Deleted} InfoType; //散列表状态

struct HEntry {
	int Data;//存放元素
	ElementType Key;//存放key值
	InfoType Info; //单元状态
};
typedef struct HEntry * HEntryPos;

struct TblNode { // 散列表类型
	int TableSize; //表的最大长度
	HEntry *Cells; //存放散列单元数据的数组
};
typedef struct TblNode *HashTable; //指向散列表

int NextPrime(int N){ /* 返回大于N且不超过MAXTABLESIZE的最小素数 */
	int i, p = (N % 2) ? N + 2 : N + 1; /*从大于N的下一个奇数开始 */

	while (p <= MAXTABLESIZE) {
		for (i = (int)sqrt(p); i > 2; i--)
			if (!(p%i)) break; /* p不是素数 */
		if (i == 2) break; /* for正常结束，说明p是素数 */
		else  p += 2; /* 否则试探下一个奇数 */
	}
	return p;
}

HashTable CreateTable(int TableSize) {
	HashTable H;

	H = (HashTable)malloc(sizeof(struct TblNode));
	H->TableSize = NextPrime(TableSize);
	H->Cells = (HEntryPos)malloc(H->TableSize * sizeof(struct HEntry));
	for (int i = 0; i < H->TableSize; i++) {
		H->Cells[i].Info = Empty;
		H->Cells[i].Data = 0;
	}
	return H;
}

Position Hash(HashTable H,ElementType key) {
	return key % H->TableSize;
}

Position Find(HashTable H,ElementType key) {
	Position now;

	for (now = Hash(H, key); H->Cells[now].Info == Legitimate; now++) {
		if (H->Cells[now].Key == key)
			return now;
		if (now == H->TableSize - 1)
			now = -1;
	}
	return now;
}

void Insert(HashTable H, ElementType key) {
	Position pos;

	pos = Find(H, key);
	H->Cells[pos].Data++;
	H->Cells[pos].Key = key;
	H->Cells[pos].Info = Legitimate;
}

int main() {
	int N,MadmanNum, Calls;
	ElementType a, b,Madman;
	HashTable H;

	cin >> N;
	H = CreateTable(2 * N);
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		Insert(H, a);
		Insert(H, b);
	}
	MadmanNum = 0;
	Calls = 0;
	Madman = 1;
	for (int i = 0; i < H->TableSize; i++) {
		if (H->Cells[i].Info != Legitimate)
			continue;
		if (H->Cells[i].Data > Calls) {
			Calls = H->Cells[i].Data;
			Madman = H->Cells[i].Key;
			MadmanNum=1;
		}
		else if(H->Cells[i].Data == Calls) {
			MadmanNum++;
			if(H->Cells[i].Key < Madman)
				Madman = H->Cells[i].Key;
		}
	}
	if (MadmanNum == 1)
		cout << Madman << ' ' << Calls;
	else
		cout << Madman << ' ' << Calls<<' '<<MadmanNum;
	return 0;
}