剣指offer-最小のk個数

タイトルの説明
n個の整数を入力し、その中で最も小さいK個の数を見つけます.例えば4,5,1,6,2,7,3,8の8つの数字を入力すると、最小の4つの数字は1,2,3,4である.
構想
この問題は簡単で、まずサイクルで整数を並べ替えてから、出力前のk個の数を出すことができますが、これでは時間の複雑度が高く、Arraysを使うとします.sortでソートすると、内部では高速ソートと最適化されたマージソートが使用されているようです.マージソートの時間複雑度はnlognで、高速ソートの平均時間複雑度もnlognですが、マージソートには追加のn参照の空間が必要です.

import java.util.Arrays;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    	Arrays.sort(input);    
    	ArrayList<Integer> nums = new ArrayList<Integer>();
    	for(int i=0;i<k;i++)
    		nums.add(input[i]);
    	return nums;
    }
}

以下は泡の順序付けの思想で、最外層はK回しか循環していない.つまり、循環ごとに最小値を配列の一番後ろに置く.もちろん、この時間の複雑さはO(N*K)であり、最適ではない.

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        if (k > input.length) {
            return al;
        }
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < input.length - i - 1; j++) {
                if (input[j] < input[j + 1]) {
                    int temp = input[j];
                    input[j] = input[j + 1];
                    input[j + 1] = temp;
                }
            }
            al.add(input[input.length - i - 1]);
        }
        return al;
    }

最も優れているのはPriorityQueueをHeapとして使用し、最大スタックでこのk個の数を保存し、毎回スタックトップと比べるだけで、スタックトップより小さい場合は、スタックトップを削除し、新しい数をスタックに入れ、時間複雑度はO(nlogk):

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
   public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
       ArrayList<Integer> result = new ArrayList<Integer>();
       int length = input.length;
       if(k > length || k == 0){
           return result;
       }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
 
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i = 0; i < length; i++) {
            if (maxHeap.size() != k) {
                maxHeap.offer(input[i]);
            } else if (maxHeap.peek() > input[i]) {
                Integer temp = maxHeap.poll();
                temp = null;
                maxHeap.offer(input[i]);
            }
        }
        for (Integer integer : maxHeap) {
            result.add(integer);
        }
        return result;
    }
}

ここでPriorityQueue構造はこのブログを参考にすることができますhttps://www.cnblogs.com/CarpenterLee/p/5488070.html