前m大的数(堆)- HDU 1280

Problem Description

还记得Gardon给小希布置的那个作业么?(上次比赛的1005)其实小希已经找回了原来的那张数表,现在她想确认一下她的答案是否正确,但是整个的答案是很庞大的表,小希只想让你把答案中最大的M个数告诉她就可以了。

给定一个包含N(N<=3000)个正整数的序列,每个数不超过5000,对它们两两相加得到的N*(N-1)/2个和,求出其中前M大的数(M<=1000)并按从大到小的顺序排列。

Input

输入可能包含多组数据,其中每组数据包括两行:

第一行两个数N和M,

第二行N个数,表示该序列。

Output

对于输入的每组数据,输出M个数,表示结果。输出应当按照从大到小的顺序排列。

Sample Input

4 4

1 2 3 4

4 5

5 3 6 4

Sample Output

7 6 5 5

11 10 9 9 8

堆排序:

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

解题思路:

这题是一个求集合中前多少名的问题,算是一个比较常用的算法,一般用堆排序解即可。但是本题有一个特点是每个数不超过5000,所以最大值也就是10000,因此可以通过数组来存储。对于任意的一个和x(x<10000),我们定义sum[x],如果sum[x]大于0,则表示有x,并且有sum[x]个。

从sum的末尾开始倒数,就是所需的序列。

扩展题(面试题):

请问如何从10亿数据中取最大的100个数据?

思路:依然是采用堆排序。但是注意10亿个数据比较大,占用内存太多,因此可以限定堆的大小为100,每次输入一个新元素时,更新堆结构,使得堆结构始终存放着最大的100个数据。

源代码:G++ 15ms

#include <stdio.h>

int main()
{
    //正整数序列
    int set[5050];
    //记录某个和所在位置的个数
    int sum[10050];

    int n, m;

    while(~scanf("%d%d", &n, &m)){
        for(int i=0; i<n;++i){
            scanf("%d", &set[i]);
        }
        //记录和的最大值
        int max = 0;
        for(int i=0; i<n; ++i){
            for(int j=i+1; j<n && i!=j; ++j){
                //两两相加
                int x = set[i] + set[j];
                //更新max
                if (x > max) {
                    max = x;
                }
                sum[x]++;
            }
        }

        //从max下标开始倒数
        for(int i= max, cnt=0; cnt<m; --i){
            //可能有多个
            while(sum[i]-- && cnt < m){
                if(cnt++ == 0){
                    printf("%d", i);
                }else{
                    printf(" %d", i);
                }
            }
        }
        printf("\n");
    }
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-03-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏韦弦的偶尔分享

Swift 两数之和 - LeetCode

13520
来自专栏微信公众号:Java团长

Java泛型详解

定义了一个List类型的集合,先向其中加入了两个字符串类型的值,随后加入一个Integer类型的值。这是完全允许的,因为此时list默认的类型为Object类型...

12620
来自专栏企鹅号快讯

1.12编程基础之函数与过程抽象/05:统计单词数

总时间限制: 1000ms 内存限制: 65536kB 描述 一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单...

286100
来自专栏赵俊的Java专栏

计算最大值

15430
来自专栏JavaEdge

Java中类型参数“<T>”和无界通配符“<?>”的区别

List<T>最应该出现的地方,应该是定义一个泛型List容器 但List是库里自带的容器,看看ArrayList的源码头一行:

36210
来自专栏数据结构与算法

23:过滤多余的空格

23:过滤多余的空格 总时间限制: 1000ms 内存限制: 65536kB描述 一个句子中也许有多个连续空格,过滤掉多余的空格,只留下一个空格。 输入一...

35840
来自专栏Bingo的深度学习杂货店

Q38 Count and Say

The count-and-say sequence is the sequence of integers with the first five terms...

36570
来自专栏数据结构与算法

26:统计满足条件的4位数个数

26:统计满足条件的4位数个数 总时间限制: 1000ms 内存限制: 65536kB描述 给定若干个四位数,求出其中满足以下条件的数的个数:  个位数上的...

47240
来自专栏ACM算法日常

Find the nth digit(二分查找) - HDU 1597

...

10220
来自专栏cs

爬虫前的准备

31960

扫码关注云+社区

领取腾讯云代金券