首页 > 试题广场 >

一个文件里有10万个随机正整数，按照以下规则能组合出一份新的

[问答题]
一个文件里有10万个随机正整数，按照以下规则能组合出一份新的数据：
A． 如果当前数字能被3整除，那么它和文件中所有数字（包括自己）两两相加后生成一组数字替代自己的位置。
B． 如果不能被3整除，则它只需要乘以二，生成一个数字替代自己的位置。
例如：[3,7,6] 会组合出[6,10,9,14,9,13,12]
再如：[5,12,9,6,2]会组合出[10,17,24,21,18,14,14,21,18,15,11,11,18,15,12,8,4]
写一个程序找出并打印出新数据的最小的前200个数字。请考虑优化算法复杂度。
添加回答
SENDOH头像 SENDOH
1.首先统计能被3整除的数的个数count，设原数组长度为len这新数组长度为len+2*count;按规则形成组合后的数组；
2，求组合后的数组的最小的前200个数，使用维持一个200个数的最大堆，将组合后的数组依次插入最大堆如果但钱数大于最大堆的堆顶元素则直接略过，如果小于则删除堆顶元素，并将此数插入最大堆，更新最大堆，最后返回这个最大堆即是数组中最小的200个数
3，算法时间复杂度O(nlog200)，空间复杂度O(n)
发表于 2015-09-03 14:25:57 回复(2)
风雪傲月头像 风雪傲月
首先构造出新的组合，然后用快速排序的思想实现新组合的部分排序，即求数组中最小的k个数
发表于 2015-09-02 11:40:33 回复(0)
提交观点

问题信息

模拟 堆 去哪儿
上传者：永梦122
难度：
2条回答 22852浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号