【题 40】最小k个数

朴灿烈づ我的快乐病毒、 2022-03-08 10:58 204阅读 0赞

【题目】  
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。  
【思路】  
1 排序，位于前k个数为最小k个数 ----------------O（nlogn）  
![在这里插入图片描述][20190315092038741.png]  
2.如果基于数组的第k个数字来调整，则使得比第k个数组小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边，这样调整以后，位于数组中左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）  
限制：需要修改输入的数组，因为函数会调整数组中数字的顺序———O（n）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
3.  
（1）创建一个大小为k的容器来存储最小的k个数字，从每次输入的n个整数中读入一个数字。  
（2）如果容器中已有数字少于k个，直接放入容器。  
（3）如果容器中已有数字达到k个，即容器已满，不能插入，只能替换。  
找到容器中k个数最大值，若最大值大于待插入数字，交换。  
如果最大值小于待插入数字，将待插入数字丢弃。  
因此，容器满了之后可以做三件事。  
（1）在k个整数中找到最大数。  
（2）可能删除这个容器中的最大数  
（3）可能插入一个新的数字  
——————————————————————————O（nlogk）  
看选择最大堆，但是代码量大，还可以采用红黑树实现容器。可以选择STL中set和multiset,(均是基于红黑树实现)参考：。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]  
【实现】

import java.util.ArrayList;
    import java.util.PriorityQueue;
    import java.util.Comparator;
    
    public class Solution {
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> result = new ArrayList<Integer>();//创建保存result的链表
            int length = input.length;//输入数组的长度
            if(k > length || k==0){//输入的k大于输入数组的长度或者k为0
                return result;
            }
            PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k,new Comparator<Integer>(){//建立大顶堆，容量为k
                @Override
                public int compare(Integer o1,Integer o2){//返回用来对此队列中的元素进行排序的比较器；如果此队列根据其元素的自然顺序进行排序，则返回 null。
                    return o2.compareTo(o1);//因为compareTo方法代表的是指定数如果大于参数的话那么则返回1，实现了comparator中重写compare方法，如果返回值是正数的话，那么就让第二个参数在前面，如果是负数的话，就让第一个数在前面。在这个方法中，如果o2大于o1那么返回1，就让o2在前面，就成为了最大堆
                }
            });
            for(int i = 0;i<length;i++){//循环遍历输入数组
                if(maxHeap.size() != k){//如果堆的大小不等于k
                    maxHeap.offer(input[i]);//将输入的第i个数进入堆
                }else if(maxHeap.peek() >input[i]){//如果堆顶数大于输入的数字
                    Integer temp = maxHeap.poll();//poll 方法每次从 PriorityQueue 的头部删除一个节点
                    temp = null;
                    maxHeap.offer(input[i]);//让小于堆顶的输入数字i进入堆
                }
            }
            for(Integer integer:maxHeap){//循环遍历最终的容量为k的maxHeap
                result.add(integer);//将maxHeap中的值加入result连编排
            }
            return result;
        }
    }

参考：  
1.《剑指offer》  
2.[https://www.nowcoder.com/profile/448404/codeBookDetail?submissionId=1505827][https_www.nowcoder.com_profile_448404_codeBookDetail_submissionId_1505827]  
![在这里插入图片描述][20190315101219557.png]  
3.[剑指offer第二版面试题40：最小的k个数（java）][offer_40_k_java]  
4。[Java堆结构PriorityQueue完全解析][Java_PriorityQueue]

[20190315092038741.png]: /images/20220308/9769eeb78f5441b7a91217c0ef3792a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220308/17d61129a359423fb0179246c8da0088.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20220308/1b0912b8ac0947aaa4ba3c12f851e9d9.png
[https_www.nowcoder.com_profile_448404_codeBookDetail_submissionId_1505827]: https://www.nowcoder.com/profile/448404/codeBookDetail?submissionId=1505827
[20190315101219557.png]: /images/20220308/16bb86f56f2a42ef94e14535b02b12f3.png
[offer_40_k_java]: https://blog.csdn.net/weixin_37672169/article/details/80921594
[Java_PriorityQueue]: https://blog.csdn.net/u013309870/article/details/71189189