剣指offerの:40最小のk個数

剣指offerの:40最小のk個数
タイトルの説明:
n個の整数を入力し、最小のk個数を見つけます.例えば、4,5,1,6,2,7,3,8の8つの数字を入力すると、最小の4つの数字は1,2,3,4である.
解法1:
入力したn個の整数を並べ替え,並べ替え後の先頭にあるk個の数が最小のk個の数である.時間複雑度O(nlogn)(高速配列).この方法は入力した配列を変更できる場合にのみ適用されます.Partitionに基づいています.
解法2:
入力した配列を変更できない場合は、最大スタックを使用できます.時間複雑度はO(nlogk).大量のデータを処理するのに適しています.まずkサイズのデータコンテナを作成して最小のk個の数字を格納し、次に入力したn個の整数から1個の数字を読み込みます.コンテナにk個未満の数字がある場合は、読み取り時に直接コンテナに格納します.コンテナにk個の数字がある場合は、コンテナがいっぱいであることを示します.この場合、これ以上挿入できません.新しい数値を入力すると、既存の数値のみが置き換えられます.既存のk個の数の最大値を見つけます.そして今回挿入する数と最大値を比較します.挿入する数が既存の最大値より小さい場合は、この数で現在の最大値を置き換えます.挿入する数が既存の最大値よりも大きい場合は、破棄できます.そのため、容器がいっぱいになったら3つのことをします:1.k個の整数の中で最大数を見つける.2.この容器から最大数を削除する可能性があります.3.新しい数値を挿入する場合があります.この容器を実現するために二叉木を使うと、この3ステップは、さらにO(logk)時間で実現することができる.したがって、n個の入力された数字に対して、総時間効率はO(nlogk)である.最大スタック:ルートノードの値は、常にそのサブツリー内の任意のノードの値よりも大きい.そこで、O(1)時間で既存のk個の数字の最大値を得ることができるが、削除および挿入操作を完了するにはO(logk)時間が必要である.
コードブロック:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {

     public static ArrayList GetLeastNumbers_Solution(int [] input, int k) {
         ArrayList rst = new ArrayList();
         if(input.length < k || k <= 0  ){
                return rst;
         }
         PriorityQueue maxHeap = new PriorityQueue<>(k, new Comparator() {
             @Override
             public int compare(Integer o1, Integer o2) {
                 return o2.compareTo(o1);
             }
         });
         for(int i = 0; i < input.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){
             rst.add(integer);
         }
         return rst;

     }

    public static void main(String[] args) {
        int input[] = {4,5,1,6,2,7,3,8};
        int k = 4;
        ArrayList a = (ArrayList) GetLeastNumbers_Solution(input, k);
        System.out.println(a);
    }
}

解法3:
最大スタックコードは比較的困難であり、我々のコンテナを実現するために、レッドブラックツリー(ツリーがある程度バランスしていることを確保する)を採用することができる.STL(standard Template Library標準テンプレートライブラリ:1.アルゴリズム2.コンテナ3.関数4.反復器)では、setとmultisetはいずれもレッドブラックツリーに基づいて実現される.
コードブロック

import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeSet;

public class Solution2redblacktree {
    public static ArrayList GetLeastNumbers(int[] input, int k){
        ArrayList list = new ArrayList();
        if(input.length <=0 || k <=0 || input.length < k){
            return list;
        }
        TreeSet kSet = new TreeSet();
        for(int i = 0 ; i < input.length; i++){
            if(kSet.size() < k){
                kSet.add(input[i]);
            }else if(input[i] < kSet.last()){
                kSet.remove(kSet.last());
                kSet.add(input[i]);
            }
        }
        Iterator iterator = kSet.iterator();
        while(iterator.hasNext()){//  if
            list.add(iterator.next());
        }
        return list;

    }