题目

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

思路

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

代码1（堆排序）

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);
        }
    }
}

关键代码

        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);
        }

代码2 找一个放置的空间

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;
}

代码3 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;
}

剑指offer---最小的K个数（堆）

题目

思路

代码1（堆排序）

代码2 找一个放置的空间

代码3 PriorityQueue