首页 > 代码库 > Hash入门
Hash入门
HDU1425
Problem Description
给你n个整数,请按从大到小的顺序输出其中前m大的数。
Input
每组测试数据有两行,第一行有两个数n,m(0<n,m<1000000),第二行包含n个各不相同,且都处于区间[-500000,500000]的整数。
Output
对每组测试数据按从大到小的顺序输出前m大的数。
Sample Input
5 3
3 -35 92 213 -644
Sample Output
213 92 3
一开始看到这题,我就直接用sort排序,然后输出了。
920MS 3640K 差点超时了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e6+10; 4 int a[N], n, m; 5 bool cmp(int x, int y){ 6 return x>y; 7 } 8 int main() 9 { 10 while(~scanf("%d %d",&n,&m)){ 11 for(int i = 0; i < n; i ++){ 12 scanf("%d",&a[i]); 13 } 14 sort(a,a+n,cmp); 15 for(int i = 0; i < m-1; i ++){ 16 printf("%d ",a[i]); 17 } 18 printf("%d\n",a[m-1]); 19 } 20 return 0; 21 }
然后用Hash做了下,发现时间快了许多。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 5e5; 4 int a[N*2+10], n, m; 5 bool cmp(int x, int y){ 6 return x>y; 7 } 8 int main() 9 { 10 while(~scanf("%d %d",&n,&m)){ 11 int tmp; 12 for(int i = 0; i < n; i ++){ 13 scanf("%d",&tmp); 14 a[tmp+N] = 1; 15 } 16 int ans = 1; 17 for(int i = 1000000; i >= 0; i --){ 18 if(a[i]){ 19 if(ans != m){ 20 ans++; 21 printf("%d ",i-N); 22 }else{ 23 printf("%d\n",i-N); 24 break; 25 } 26 } 27 } 28 } 29 return 0; 30 }
常用的Hash函数具体有:SDBMHash,RSHash,JSHash,ELFHash,BKDRHash,DJBHash等等。以后要好好的学了。
Hash入门
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。