Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic Discuss
Problem Description
在n个数中，找出出现次数最多那个数字，并且输出出现的次数。如果有多个结果，输出数字最小的那一个。
Input
单组数据，第一行数字n（1<=n<=100000)。
接下来有n个数字，每个数字不超过100000000
Output
出现次数最多的数字和次数。
Sample Input
3
1 1 2Sample Output
1 2Hint
Source
cz
注意：正常的存表方法会出错，本来想的是每出现一个数，对应的表中数值加1,再将这个表进行分析，但即使解决了最大数字的问题，相同数字的值的问题只能通过for循环下标替换来实现。但不可避免的，对于大数字的时间复杂度是无法处理的。因此学习了用链表的解法，所有模10的6次方得出的值相同的数被存在同一个链表里，为此还复习了很久的链表，又忘了typedef struct Node的正确写法，每次写链表都得复习一遍。这个代码需要反复去看，关于链表链接，链表遍历，链表初次创建时的语句都很重要
代码：
#include <iostream>
#include <stdlib.h>
#include <stdio.h>using namespace std;typedef struct Node
{int data;int Count;struct Node *next;
} lnode,*linklist;linklist head[100000];int Max;
int num;void Find(int key)
{int y=key%100000;linklist p,q;p=head[y]->next;q=head[y];while(p!=NULL){if(p->data==key){p->Count++;if(Max<p->Count){Max=p->Count;num=p->data;}else if(Max==p->Count){if(num>=p->data){num=p->data;}}break;}q=p;p=p->next;}if(p==NULL){linklist r;r=(lnode*)malloc(sizeof(lnode));r->Count=1;r->data=key;if(Max<r->Count){Max=r->Count;num=r->data;}else if(Max==r->Count){if(num>=r->data){num=r->data;}}q->next=r;r->next=NULL;}//此处相当于head之后没有连接新的链表结点
}int main()
{int n;cin>>n;int key=0;for(int i=0; i<100000; i++){head[i]=(lnode*)malloc(sizeof(lnode));head[i]->next=NULL;}for(int i=0; i<n; i++){cin>>key;Find(key);}cout<<num<<" "<<Max<<endl;return 0;
}