Day3：Hash的应用

Hash思想

使用存储位置与数据本身对应起来的存储手段。

例3.1 统计同成绩学生人数

时间限制：1s 内存限制：32M

题目描述

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

输入描述:

测试输入包含若干测试用例，每个测试用例的格式为
第1行：N
第2行：N名学生的成绩，相邻两数字用一个空格间隔。
第3行：给定分数
当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。

输出描述:

对每个测试用例，将获得给定分数的学生人数输出。

示例输入

3
80 60 90
60
2
85 66
0
5
60 75 90 55 75
75
0

示例输出

1
0
2

3.1代码

#include <stdio.h>

int main()
{
    int n;
    while(scanf("%d", &n) != EOF && n != 0)
    {
        int buf[101]={0}; //成绩在0-100之间，成绩计数数组初始为0
        for(int i = 0; i < n; i++){
            int temp;
            scanf("%d", &temp); //每次输入的成绩暂存到temp中
            buf[temp] ++;       //buf数组对应成绩下标位置计数+1，如输入80，则buf[80]计数加1
        }
        int x; //给定查询的分数
        scanf("%d", &x);
        printf("%d\n", buf[x]);
    }
    return 0;
}

例3.2 Sort

时间限制：1s 内存限制：128M

题目描述

给你n个整数，请按从大到小顺序输出其中前m大的数。

输入描述:

各组测试数据有两行，第一行有两个数n,m(0<n,m<1000000),第二行包含n个各不相同，且处于区间[-500000,500000]的整数。

输出描述:

对每组测试数据按从大到小的顺序输出前m大的数。

示例输入

5 3
3 -35 92 213 -644

示例输出

213 92 3

分析

由于本题待排序数字十分庞大(1000000)，即使使用时间复杂度为O(nlogn)的快速排序来解决该问题，时间复杂度也会达到千万数量级，超过了1s时限。而若用Hash的思想，用一个数组来统计每一种数字是否出现，空间复杂度在限定范围内，且统计出现数字当中较大的m个数字，也仅需从尾到头遍历该数组，时间复杂度在百万级别内，符合题目要求。

3.2代码

//Hash的应用，对每组测试数据按从大到小的顺序输出前m大的数

#include <stdio.h>
#define OFFSET 500000  //偏移量，使得输入[-500000,500000]映射到[0,1000000]区间中
int buf[1000001];

int main()
{
    int n,m;
    while(scanf("%d%d", &n,&m) != EOF)
    {
        for (int i = 0; i <= 1000000; i++)
        {
            buf[i] = 0;  //初始时，每个数字都标记为未出现。
        }
        for(int i = 0; i < n; i++)  //标记输入的n个数。如输入10则buf[10+OFFSET]中标记为1
        {
            int temp;
            scanf("%d", &temp);
            buf[temp + OFFSET] = 1;
        }
        for(int i = 1000000; i >= 0; i--)
        {
            if( buf[i] == 1 )
            {
                printf("%d", i - OFFSET);
                m --;
                if(m != 0){
                    printf(" ");
                }
                else{
                    printf("\n");
                    break;
                }
            }
        }
    }
    return 0;
}

最后编辑于：2020.02.04 20:43:12