3. Hash的应用

题目来源和说明

2006年浙江大学计算机研究生机试真题，试图通过本次题解总结和梳理哈希类问题的所有复试题目。代码模板参考王道考研机试

题目描述

读入N名学生的成绩，将获得某一给定分数的学生人数输出

样例

测试输入包含若干测试用例，每个测试用例的格式为


第1行：N
第2行：N名学生的成绩，相邻两数字用一个空格间隔。
第3行：给定分数

当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。

C++ 代码

#include<iostream>
using namespace std;
int main() {
    int n;
    while(scanf("%d",&n)!=EOF&&n!=0) { 
        int Hash[101]={0}; //建立一个初始为0的Hash数组用来记录各种分数出现的次数
        for(int i=0;i<n;i++) {
            int x;
            scanf("%d",&x);
            Hash[x]++; //统计分数出现的次数
        }
        int x;
        scanf("%d",&x);
        printf("%d\n",Hash[x]);
    }
    return 0;
}

同类题目

1. Sort:

https://www.cnblogs.com/codershell/archive/2013/09/05/3304260.html

简要分析

1. 刚看到这个问题，maybe脑袋中出现很多排序方法。但是千万不能忽视时间复杂度的问题。时间复杂度问题：注意到m的级别是千万级别，即便用快排（时间复杂度nlogn）也无法将问题降至百万级别，因此我初步想到了两种方法。一种是堆排序，因为调整堆的时间复杂度为O(logn），共计调整m次就行。因此可以降至百万级别。但是考虑到建堆的时间复杂度是O（n），这种方法可能可以，但是我没有测试。另一种方法是看到例题中限定了输入的数字一定是[-500000,500000]区间内的整数，且各不相同。那何不利用哈希的思想，直接用一个数组分别统计每一种数字是否出现，牺牲空间将时间复杂度降低了100万的级别。下面是第二种方法的C++代码。

C++代码

#include<iostream>
using namespace std;
#define OFFSET 500000 //偏移量，用于补偿实际数字和下标之间的偏移
int Hash[1000001];//不出现为0，出现后标记为1

int main() {
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF) {
        for(int i=-500000;i<=500000;i++) {
            Hash[i+OFFSET]=0; //初始化，将每个数字都标记为未出现
        }
        for(int i=1;i<=n;i++) {
            int x;
            scanf("%d",&x);
            Hash[x+OFFSET]=1; //出现的数字，设置成1
        }
        for(int i=500000;i>=-500000;i--) {
            if(Hash[i+OFFSET]==1) {
                printf("%d",i); //输出改个数字
                m--;
                if(m!=0) printf(" "); //如果m个数字没有输出完成，则直接输出一个空格
                else {
                    printf("\n");
                    break;
                }
            }
        }
    }
    return 0;
}

2. 谁是你的潜在朋友

简要分析

这个题目是应该想要获得喜欢每本书的人数-1，即是结果。因此，以每本书的id为Hash的横坐标，喜欢i号书的人的数目作为纵坐标建立hash就可以啦~。

C++代码

#include<iostream>
using namespace std;
int Hash[205]={0};
int Love[200]={0};
int main() {
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF) {
        for(int i=1;i<=n;i++) {
            int x;
            scanf("%d",&x);
            Love[i]=x;
            Hash[x]++;
        }
        for(int i=1;i<=n;i++) {
            if(Hash[Love[i]]==1) 
                printf("BeiJu\n");
            else printf("%d\n",Hash[Love[i]]-1);
        }
    }
    return 0;
}

3.剩下的树

简要分析

这个问题看是很复杂，其实只要不考虑空间复杂度，用Hash的思想和数组表示树是否存在即可。比如假设长度是L，则我们定义hash数组Hash[L+1],其中Hash[i]表示第i个节点是否存在树。初始化全为1，表示都有树，然后对于不同区间，分别置对应的Hash[i]为0即可。最后从0到L数一下1的个数就可以了。

C++代码

#include<iostream>
using namespace std;
int Hash[10005]; 
int main() {
    int n,m;
    int l,r;
    int res=0;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=0;i<=n;i++) 
            Hash[i]=1; //初始化全部载了树
        for(int i=0;i<m;i++) {
            scanf("%d%d",&l,&r);
            for(int i=l;i<=r;i++) Hash[i]=0;
        }
        for(int i=0;i<=n;i++) {
            if(Hash[i])res++;
        }
        printf("%d\n",res);
    }
    return 0;
}