最小的K个数
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
本题无非就是排序，取前K个值。但选什么排序算法呢？
基于堆排序算法，构建最大堆。时间复杂度为O(nlogk)；
如果用快速排序，时间复杂度为O(nlogn)；
如果用冒泡排序，时间复杂度为O(n*k)；
这类题目要考的应该是堆排序的改造。在n 较大，k较小的情况下。
改造的堆排序：
1.将前k个元素构造成最大堆（0~k-1）
2.从k位开始，依次与最大堆的堆顶元素进行比较。如果比堆顶小，则该数与堆顶交换位置，维护最大堆
3.最后从k-1~0的数是最小的k的数
思考：
为什么在求最小的k个数，不是建立最小堆而是建立最大堆？？？
建立最大堆的情况下，判断从k~n-1位的数是否有可能是最小的k个数，只需与堆根进行比较，当它比跟堆大的时候，它肯定比堆内其他数都大，即它无希望排进前K个数。若有希望排进，那么需将目前堆内最大的数赶出，正好又是堆根，两者交换即可。
代码：
import java.util.*;public class Solution {public ArrayList<Integer>GetLeastNumbers_Solution(int[] input, int k) {ArrayList<Integer> array = new ArrayList<Integer>();if(input==null||input.length==0||k<=0||k>input.length){return array;}for(int i=k/2-1;i>=0;i--){buildMaxHeapSort(input,i,k);}for(int j=k;j<input.length;j++){if(input[j]<input[0]){swap(input,0,j);buildMaxHeapSort(input,0,k);}}for(int i=k-1;i>=0;i--){array.add(input[i]);}return array;}public void buildMaxHeapSort(int[] input,int i,int k){int leftchild=2*i;int rightchild=2*i+1;int larget=i;if(leftchild<k&&input[i]<input[leftchild]){larget=leftchild;}if(rightchild<k&&input[larget]<input[rightchild]){larget=rightchild;}if(larget!=i){swap(input,i,larget);buildMaxHeapSort(input,larget,k);}}public void swap(int[] input,int a,int b){int temp=input[a];input[a]=input[b];input[b]=temp;}}
如果觉得《剑指offer_输入n个整数 找出其中最小的K个数》对你有帮助，请点赞、收藏，并留下你的观点哦！
