admin 管理员组文章数量: 1086019
找出最大的k个数
这是一个算法中很常见的问题，遇到这个题开始像我这种还未养成算法思维的人，第一想法就是先排序然后直接去前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大的数。
未完待续…
本文标签： 找出最大的k个数
版权声明：本文标题：找出最大的k个数 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1686558455a10131.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论