最小的K个数

题目

输入n个整数&＃xff0c;找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字&＃xff0c;则最小的4个数字是1,2,3,4。

思路

最简单的方法就是先排序&＃xff0c;然后在遍历输出最小的K个数&＃xff0c;方法简单粗暴。

代码

import java.util.ArrayList;
public class Solution {public ArrayList GetLeastNumbers_Solution(int [] input, int k) {ArrayList returnList &＃61; new ArrayList<>();if(input &＃61;&＃61; null || input.length &＃61;&＃61;0 || k <1 || k>input.length){return returnList;}int[] ks &＃61; new int[k];for(int i &＃61;0;i&＃61;0;i--){toHeap(ks,i,ks.length);}for(int i &＃61;k;i input[index]){index &＃61; left;}while(right input[index]){index &＃61; right;}if(index !&＃61;start){int temp &＃61; input[start];input[start] &＃61; input[index];input[index] &＃61; temp;toHeap(input,index,end);}}
}

代码1 找一个放置的空间

public ArrayList GetLeastNumbers_Solution(int [] input, int k) {List list &＃61; new ArrayList();if (k>input.length || k&＃61;&＃61;0) {return (ArrayList)list;}for (int i &＃61; 0; i }


代码2 PriorityQueue

public static void main(String[] args) {int [] input &＃61; {4,5,1,6,2,7,3,8};System.out.println(GetLeastNumbers_Solution(input,4));
}public static ArrayList GetLeastNumbers_Solution(int [] input, int k) {ArrayList list &＃61; new ArrayList<>();if (input &＃61;&＃61; null || k <&＃61; 0 || k > input.length || input.length&＃61;&＃61;0) {return list;}PriorityQueue pq &＃61; new PriorityQueue<>(k, new Comparator(){&＃64;Overridepublic int compare(Integer o1, Integer o2){return o2 - o1;}});for(int i&＃61;0; i}


代码3

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Arrays;
public class Solution {
public ArrayList GetLeastNumbers_Solution(int[] input, int k) {ArrayList list &＃61; new ArrayList<>();if (input &＃61;&＃61; null || k <&＃61; 0 || k > input.length) {return list;}int[] kArray &＃61; Arrays.copyOfRange(input, 0, k);//1.构建大顶堆for(int i&＃61;kArray.length / 2 - 1;i>&＃61;0;i--){//从第一个非叶子节点开始&＃xff0c;下次第二个&＃xff0c;依次调整构建大根堆adjustHeap(kArray,i,kArray.length);}//2.依次来判断&＃xff0c;有小于堆顶的那就替换掉继续调整一个堆for (int i &＃61; k; i &＃61; 0; i--) {list.add(kArray[i]);}return list;}public static void adjustHeap(int []arr,int i,int length){ //从i节点开始调整&＃xff0c;int temp &＃61; arr[i];//先取出当前元素ifor(int k &＃61; i*2&＃43;1;ktemp){//如果子节点大于父节点&＃xff0c;将子节点值赋给父节点&＃xff08;不用进行交换&＃xff09;arr[i] &＃61; arr[k];i &＃61; k;}else{break;}}arr[i] &＃61; temp;//将temp值放到最终的位置}


代码4

用前K个数建立最大堆,每次用堆顶元素和n-k中各个元素比较,如果堆顶元素较大,则互换位置,然后调整堆,使之重新成为最大堆。时间复杂度

O&＃xff08;n*logk&＃xff09;

import java.util.ArrayList;/*** &＃64;Auther: liuhaidong* Data: 2020/1/14 0014、14:05* Description:* &＃64;version: 1.0*/
public class Test17 {public static void main(String[] args) {int [] arr &＃61;{4,5,1,6,2,7,3,8};System.out.println(GetLeastNumbers_Solution(arr,4));}public static ArrayList GetLeastNumbers_Solution(int [] ins, int k) {if(ins &＃61;&＃61; null || k>ins.length){return new ArrayList<>();}int[] ks &＃61; new int[k];// 最先遍历的k个数放入数组中 o(k)for (int i &＃61; 0; i &＃61; 0; i--) {maxHeap(ks, ks.length, i);}//n-k个数和前面和k中最大数比较for (int i &＃61;k; i ins[i]){ks[0]&＃61;ins[i];//调整堆,堆顶被替换了,加入被替换的值非常小,会一直下沉到叶子节点.maxHeap(ks,ks.length,0);}}ArrayList lists &＃61; new ArrayList<>();// 输出最小的K个数for (int i &＃61; 0; i array[largest]) {largest &＃61; left;}//判断有没有右节点,如若有则largest和右节点比较,注意largest有可能是left也有可能是indexif (right array[largest]) {largest &＃61; right;}if (index !&＃61; largest) {int temp &＃61; array[index];array[index] &＃61; array[largest];array[largest] &＃61; temp;//被替换的largest节点所在的堆,需要重新调整,使小值/大值一直下沉maxHeap(array, heapSize, largest);}}
}


关键代码

int[] ks &＃61; new int[k];// 最先遍历的k个数放入数组中 o(k)for (int i &＃61; 0; i &＃61; 0; i--) {maxHeap(ks, ks.length, i);}

这个代码相当于构建堆

参考网站 bilibili.com/video/av47196993/