首页 > 其他 > 详细

机试指南第二章-经典入门-Hash的应用自解

时间:2019-06-15 20:07:09      阅读:38      评论:0      收藏:0      [点我收藏+]

标签:相同   ont   dex   space   down   内存限制   size   com   数据   

Hash的应用:

Hash即散列,不像数据结构与算法中讲的各种Hash方法和冲突处理等过多的阐述,以下主要介绍Hash在机试试题解答中的作用。

例2.5 统计同成绩学生人数

Hash解法AC代码:(一般想到的也是这种解法)

#include<cstring>
#include<iostream>
using namespace std;

int grade[105];

int main()
{
    int n, m, index;
    memset(grade, 0, sizeof(grade));
    while (cin >> n)
    {
        for (int i = 0; i < n; i++)
        {
            cin >> m;
            grade[m]++;
        }
        cin >> index;
        cout << grade[index] << endl;
    }
    return 0;
}

例2.6 Sort

时间限制:1 秒 内存限制:128 兆

题目描述:

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

输入:

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

输出:

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

样例输入:

5 3 3 -35 92 213 -644

样例输出:

213 92 3 

AC代码:

#include<cstring>
#include<iostream>

using namespace std;

int num[1000001];
const int UPSET = 500000;
const int DOWNSET = -500000;

int main()
{
    int n, m, x;
    memset(num, 0, sizeof(num));
    while (cin >> n >> m)
    {
        for (int i = 0; i < n; i++)
        {
            cin >> x;
            num[x+ UPSET]++;
        }
        for (int i = UPSET; i >= DOWNSET; i--)
        {
            if (num[i + UPSET] == 1)
            {
                cout << i;
                m--;
                if (m != 0)cout << " ";
                else
                {
                    cout << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

 

机试指南第二章-经典入门-Hash的应用自解

标签:相同   ont   dex   space   down   内存限制   size   com   数据   

原文:https://www.cnblogs.com/yun-an/p/11028552.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号