2011-12-08 09:21:40Morris
[UVA] 484 - The Department of Redundancy Department
The Department of Redundancy Department
| The Department of Redundancy Department |
Write a program that will remove all duplicates from a sequence of integers and print the list of unique integers occuring in the input sequence, along with the number of occurences of each.
Input
The input file will contain a sequence of integers (positive, negative, and/or zero). The input file may be arbitrarily long.
Output
The output for this program will be a sequence of ordered pairs, separated by newlines. The first element of the pair must be an integer from the input file. The second element must be the number of times that that particular integer appeared in the input file. The elements in each pair are to be separated by space characters. The integers are to appear in the order in which they were contained in the input file.
Sample Input
3 1 2 2 1 3 5 3 3 2
Sample Output
3 4 1 2 2 3 5 1
作法 : HASH, 不用循序搜尋
#include<stdio.h>
#include<string.h>
#define Mod 100000
#define MaxL 1000000
int HASH[Mod], size;
typedef struct {
int v, time, next;
}C;
C Node[MaxL];
int insHash(int v) {
int m = ((v%Mod)+Mod)%Mod;
int now = HASH[m], pre = 0;
while(now) {
if(Node[now].v < v)
pre = now, now = Node[now].next;
else if(Node[now].v == v) {
Node[now].time++;return 1;
} else {
break;
}
}
size++;
if(!pre) HASH[m] = size;
else Node[pre].next = size;
Node[size].v = v, Node[size].time = 1;
Node[size].next = now;
return 0;
}
int main() {
int n, i;
memset(HASH, 0, sizeof(HASH));
size = 0;
while(scanf("%d", &n) == 1)
insHash(n);
for(i = 1; i <= size; i++)
printf("%d %d\n", Node[i].v, Node[i].time);
return 0;
}