您好,欢迎来到微智科技网。
搜索
您的当前位置:首页找到无序数组中最小的k个数

找到无序数组中最小的k个数

来源:微智科技网

题目:给定一个无序整数数组arr,找到其中最小的k个数

要求:如果数组arr的长度为n,排序之后自然可以得到最小的k个数,此时时间复杂度与排序的时间复杂度相同均为O(NlogN),本题要求实现时间复杂度为O(NLogK).

1.O(NLogK)的方法,即一直维护一个有k个数的最大的大根堆,这个堆是目前选出的k个最小数,在堆里的k个元素中堆顶的元素是最大的一个。

接下来遍历整个数组,遍历的过程中看当前数是否比堆顶元素小。如果是,就把堆顶的元素替换成当前的数,然后从堆顶的位置调整堆,替换后堆的最大元素的位置依旧在堆顶;如果不是,则不进行任何操作,继续遍历下一个数;遍历完成后,堆中的k个数就是所有数组中最小的k个数。

具体请参看如下代码中的getMinKNumsByHeap方法,代码中的heapInsert和heapify方法分别为堆排序中的建堆和调整堆的实现。

 

转载于:https://www.cnblogs.com/guanling222/p/5771180.html

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- 7swz.com 版权所有 赣ICP备2024042798号-8

违法及侵权请联系:TEL:199 18 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务