首页 > 代码库 > Hash入门

Hash入门

2024-09-30 14:40:01   215人阅读

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入门


联系
我们