【上海校区】利用堆排序解决找出最小的k个值问题

python 未结 0 77
全网营销推广
全网营销推广 2021-07-22 15:32
悬赏:16
题目描述
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

分析
问题很简单,升序排序后直接输出前k个,不过要考虑时间复杂度的问题。可以用堆排序,构建有k个值的大顶堆,然后用堆头部与其他值比较,堆头部值较大则调换值,并调整,最后k个值为最小的几个。时间复杂度为nlogk。

代码
import java.util.ArrayList;

public class HeapKthMin {

       
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[] nums = {6,7,5,1,9,8,2,3,4};
                ArrayList<Integer> list = getLeastNumber(nums, 5);
                for(int num: list){
                        System.out.println(num);
                }
               
        }
       
        public static ArrayList<Integer> getLeastNumber(int[] input, int k){
                ArrayList<Integer> res = new ArrayList<>();
                if(input==null || input.length==0 || input.length<k){
                        return res;
                }
                for(int i=k/2-1; i>=0; i--){
                        adjustHeap(input, i, k-1);
                }
                for(int i=k; i<input.length; i++){
                        if(input < input[0]){
                                int temp = input;
                                input = input[0];
                                input[0] = temp;
                                adjustHeap(input, 0, k-1);
                        }
                }
                for(int i=0; i<k; i++){
                        res.add(input);
                }
                return res;
        }
       
        public static void adjustHeap(int[] nums, int position, int length){
                int temp = nums[position];
                int child = 2*position+1;
                for(; child<=length; child=child*2+1){
                        if(child<length && nums[child]<nums[child+1]){
                                child++;
                        }
                        if(temp>nums[child]){
                                break;
                        }
                        nums[position] = nums[child];
                        position = child;
                }
                nums[position] = temp;
        }

}

---------------------
作者:另一个我竟然存在
来源:CSDN
原文:https://blog.csdn.net/qq_24034545/article/details/83754950
版权声明:本文为博主原创文章,转载请附上博文链接!

相关标签:
回答
  • 消灭零回复
提交回复