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

Hash的应用：

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

Hash解法AC代码：（一般想到的也是这种解法）

#include<cstring>

#include<iostream>

using namespace std;

int grade[];

int main()

{

    int n, m, index;

    memset(grade, , sizeof(grade));

    while (cin >> n)

    {

        for (int i = ; i < n; i++)

        {

            cin >> m;

            grade[m]++;

        }

        cin >> index;

        cout << grade[index] << endl;

    }

    return ;

}

例2.6 Sort

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

题目描述：

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

输入：

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

输出：

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

样例输入：

   -   -

样例输出：

AC代码：

#include<cstring>

#include<iostream>

using namespace std;

int num[];

const int UPSET = ;

const int DOWNSET = -;

int main()

{

    int n, m, x;

    memset(num, , sizeof(num));

    while (cin >> n >> m)

    {

        for (int i = ; i < n; i++)

        {

            cin >> x;

            num[x+ UPSET]++;

        }

        for (int i = UPSET; i >= DOWNSET; i--)

        {

            if (num[i + UPSET] == )

            {

                cout << i;

                m--;

                if (m != )cout << " ";

                else

                {

                    cout << endl;

                    break;

                }

            }

        }

    }

    return ;

}

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int a[];

bool cmp(int a,int b)

{

    return a > b;

}

int main()

{

    int n, m;

    while (scanf("%d%d", &n, &m) != EOF)

    {

        for (int i = ; i < n; i++)scanf("%d", &a[i]);

        sort(a, a + n, cmp);

        for (int i = ; i < m - ; i++)printf("%d ", a[i]);

        printf("%d\n", a[m-]);

    }

    //system("pause");

    return ;

}

二刷

巴特西

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

最新文章

热门文章