一道TOPK问题

今天遇到一道TOP k的变形题,题目大概意思是有10W个随机整数,然后对这些数进行如下操作:

1.当能被3整除时,将此数替换为此数和其它数两两相加的数,包括数本身

2.当不能被3整除时,将此数替换为原数的两倍

问当变换后的数中,输出最小的K个数,复杂度尽可能低

解:

此题可以先对10W个数用partition的思想,找出最小的K个数,然后对K个数进行排序,接着开始遍历K个数

假设k个数分别是    a1,  a2,    a3,   a4,.........ak,若此时k个数都不能被3整除,则最小的k个数为

2a1,2a2,2a3,2a4,.........2ak,此时这即为最小的K个数,如果其中ai是第一个能被3整除的数,那此时就会

2a1 ------------2ai中加入a1+ai,a2+ai.......ai-1+ai这i-1个数,所以,此时算法就是从头开始遍历,分两种情况

ai能被3整除,则加入a1+ai,a2+ai.......ai+ai,

ai不能被3整除,则加入2ai

当已经有K个数了,则退出循环。

代码就不写了,思想有了,代码实现起来还是很简单的。

上一篇:Ubuntu 16.04安装、卸载mysql及怎么使用SQL常用操作语句


下一篇:11 款最好 CSS 框架 让你的网站独领风骚