这是一个算法中很常见的问题,遇到这个题开始像我这种还未养成算法思维的人,第一想法就是先排序然后直接去前K个大的数就好。
但居然在笔试中遇到这个题,那最最普通的这种解法肯定肯定是无法满足结果的。
而且一旦数据量一大,即便排序效率高也需要花上不少时间。这里不再谈普通的解决方法。
第二种解法是利用快排算法,做相应改变,执行有限次数获取前K大的数。
假设N个数存储在集合S中,从S中 随机 取一个数X,把集合内数分成两部分,比X大的数置于 S a S_a Sa中,比X小的置于 S b S_b Sb中。
这样就有了两个情况:
S a S_a Sa中元素的个数小于K, S b S_b Sb中所有元素中 K-| S a S_a Sa|个最大的数与 S a S_a Sa中所有元素组合起来就是需要求前K大的元素。
S a S_a Sa中元素的个数大于K,则需要返回 S a S_a Sa中最大的K个数。
这样做递归运算。见大问题分解成小问题,平均运算时间复杂度O(N* l o g 2 K log_2K log2K)。这样一看的话,这个要比先进行完整的快排,要快很多。
代码:
/**
* 寻找最大的K个数
*/
class MaxK {
fun kBig(arr: ArrayList<Int>, k: Int): ArrayList<Int> {
if (k <= 0) {
return arrayListOf()
}
if (arr.size <= k) {
return arr
}
val (sa, sb) = partition(arr)
val resultA = kBig(sa, k)
val resultB = kBig(sb, k - sa.size)
resultA.addAll(resultB)
return resultA
}
private fun partition(s: ArrayList<Int>): Result {
val pivot = s[0]
val sa = arrayListOf<Int>()
val sb = arrayListOf<Int>()
for (i in 1 until s.size) {
val element = s[i]
if (element < pivot) sb.add(element) else sa.add(element)
}
if (sa.size < sb.size) sa.add(pivot) else sb.add(pivot)
return Result(sa, sb)
}
}
data class Result(var sa: ArrayList<Int>, var sb: ArrayList<Int>)
这里使用了解构声明方式返回,因此定义了一个data class的Result类。
解法三:找到N个数中最大的K个数,本质就是要找到最大的K个中最小的那个,即第K大的数。
手机扫一扫
移动阅读更方便
你可能感兴趣的文章