最小的K个数
题目
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
思路
最简单的方法就是先排序，然后在遍历输出最小的K个数，方法简单粗暴。
代码
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> returnList = new ArrayList<>();
if(input == null || input.length ==0 || k <1 || k>input.length){
return returnList;
}
int[] ks = new int[k];
for(int i =0;i<k;i++){
ks[i] = input[i];
}
for(int i =(ks.length-1)/2;i>=0;i--){
toHeap(ks,i,ks.length);
}
for(int i =k;i<input.length;i++){
if(input[i] < ks[0]){
ks[0] = input[i];
toHeap(ks,0,ks.length);
}
}
for(int i =0;i<k;i++){
returnList.add(ks[i]);
}
return returnList;
}
public void toHeap(int [] input,int start,int end){
int index = start;
int left = index*2+1;
int right = index*2+2;
while(left < end && input[left] > input[index]){
index = left;
}
while(right < end && input[right] > input[index]){
index = right;
}
if(index !=start){
int temp = input[start];
input[start] = input[index];
input[index] = temp;
toHeap(input,index,end);
}
}
}
代码1 找一个放置的空间
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
List<Integer> list = new ArrayList<Integer>();
if (k>input.length || k==0) {
return (ArrayList)list;
}
for (int i = 0; i < k; i++) {
list.add(input[i]);
}
for (int i = k; i < input.length; i++) {
Collections.sort(list);
if(input[i] < list.get(k-1)){
list.set(k-1, input[i]);
}
}
return (ArrayList)list;
}
代码2 PriorityQueue
public static void main(String[] args) {
int [] input = {4,5,1,6,2,7,3,8};
System.out.println(GetLeastNumbers_Solution(input,4));
}
public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if (input == null || k <= 0 || k > input.length || input.length==0) {
return list;
}
PriorityQueue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2){
return o2 - o1;
}
});
for(int i=0; i<input.length; i++){
if(pq.isEmpty() || pq.size()<k)
{
pq.add(input[i]);
}
else{
if(input[i]<pq.peek()){
pq.poll();
pq.add(input[i]);
}
}
}
while(!pq.isEmpty()){
list.add(pq.poll());
}
return list;
}
代码3
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Arrays;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if (input == null || k <= 0 || k > input.length) {
return list;
}
int[] kArray = Arrays.copyOfRange(input, 0, k);
//1.构建大顶堆
for(int i=kArray.length / 2 - 1;i>=0;i--){
//从第一个非叶子节点开始，下次第二个，依次调整构建大根堆
adjustHeap(kArray,i,kArray.length);
}
//2.依次来判断，有小于堆顶的那就替换掉继续调整一个堆
for (int i = k; i < input.length; i++) {
if (input[i] < kArray[0]) {
kArray[0] = input[i];
adjustHeap(kArray, 0, kArray.length);
}
}
//最后把堆里的元素读出来
for (int i = kArray.length - 1; i >= 0; i--) {
list.add(kArray[i]);
}
return list;
}
public static void adjustHeap(int []arr,int i,int length){
//从i节点开始调整，
int temp = arr[i];//先取出当前元素i
for(int k = i*2+1;k<length;k = k*2+1){
//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){
//如果左子结点小于右子结点，k指向右子结点
k++;
}
if(arr[k] >temp){
//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;
//将temp值放到最终的位置
}
代码4
用前K个数建立最大堆,每次用堆顶元素和n-k中各个元素比较,如果堆顶元素较大,则互换位置,然后调整堆,使之重新成为最大堆。时间复杂度
O（n*logk）
import java.util.ArrayList;
/**
* @Auther: liuhaidong
* Data: 2020/1/14 0014、14:05
* Description:
* @version: 1.0
*/
public class Test17 {
public static void main(String[] args) {
int [] arr ={4,5,1,6,2,7,3,8};
System.out.println(GetLeastNumbers_Solution(arr,4));
}
public static ArrayList<Integer> GetLeastNumbers_Solution(int [] ins, int k) {
if(ins == null || k>ins.length){
return new ArrayList<>();
}
int[] ks = new int[k];
// 最先遍历的k个数放入数组中 o(k)
for (int i = 0; i < k; i++) {
ks[i] = ins[i];
}
int half = (ks.length-1) / 2;
for (int i = half; i >= 0; i--) {
maxHeap(ks, ks.length, i);
}
//n-k个数和前面和k中最大数比较
for (int i =k; i < ins.length; i++) {
//如果堆顶大于n-k中数,则交换位置
if(ks[0]>ins[i]){
ks[0]=ins[i];
//调整堆,堆顶被替换了,加入被替换的值非常小,会一直下沉到叶子节点.
maxHeap(ks,ks.length,0);
}
}
ArrayList<Integer> lists = new ArrayList<>();
// 输出最小的K个数
for (int i = 0; i < k; i++) {
lists.add(ks[i]);
}
return lists;
}
public static void maxHeap(int[] array, int heapSize, int index) {
int left = index * 2 + 1;
int right = index * 2 + 2;
int largest = index;
//判断有没有左节点,如若有则比较替换largest
if (left < heapSize && array[left] > array[largest]) {
largest = left;
}
//判断有没有右节点,如若有则largest和右节点比较,注意largest有可能是left也有可能是index
if (right < heapSize && array[right] > array[largest]) {
largest = right;
}
if (index != largest) {
int temp = array[index];
array[index] = array[largest];
array[largest] = temp;
//被替换的largest节点所在的堆,需要重新调整,使小值/大值一直下沉
maxHeap(array, heapSize, largest);
}
}
}
关键代码
int[] ks = new int[k];
// 最先遍历的k个数放入数组中 o(k)
for (int i = 0; i < k; i++) {
ks[i] = ins[i];
}
int half = (ks.length-1) / 2;
for (int i = half; i >= 0; i--) {
maxHeap(ks, ks.length, i);
}
这个代码相当于构建堆
参考网站 bilibili.com/video/av47196993/
