剣指offer--30.最小k個数

タイトル:n個の整数を入力して、その中の最小のk個の数を探し出して、eg、input={4,5,1,6,2,7,3,8}を入力して、最小の4個の数は1,2,3,4です
構想:入力したn個の整数を並べ替えて、並べ替えた後に最も前に位置するk個の数は最小のk個の数で、アルゴリズムの時間の複雑度はO(nlogn)です

       public static ArrayList GetLeastNumbers_Solution(int [] input, int k) {
		ArrayList list=new ArrayList<>();
		if(input==null || k<=0 || k>input.length){
			return list;
		}
		Arrays.sort(input);
		for(int i=0;i

剣指offer解法1:Partition関数に基づいて配列のk番目の数字に基づいて調整し、k番目の数字より小さいすべての数字が配列の左側に位置し、k番目の数字より大きいすべての数字が配列の右側に位置するように調整する.このように調整した後、配列の左端に位置するk番目の数字は最小のk個の数字であるが、このk個の数字は必ずしもソートされていない

import java.util.*;
public class wr30MinKNumber {
	
	public static ArrayList GetLeastNumbers_Solution(int [] input, int k) {
		ArrayList list=new ArrayList<>();
		if(input==null || k<=0 || k>input.length){
			return list;
		}
		Arrays.sort(input);
		for(int i=0;i getLeastNumbers(int []input,int k){
		ArrayList list=new ArrayList<>();
		if(input==null || k>input.length || k<=0){
			return list;
		}
		int low=0;
		int high=input.length-1;
		int index=Partition(input,k,low,high);
		while(index!=k-1){
			if(index>k-1){
				index=Partition(input,k,low,index-1);
			}else{
				index=Partition(input,k,index+1,high);
			}
		}
		for(int i=0;i=key){
				high--;
			}
			swap(input,low,high);
			while(low list=GetLeastNumbers_Solution(input,4);
		ArrayList list=getLeastNumbers(input,4);
		for(int i:list){
			System.out.print(i+" ");
		}		
	}
}

剣指offer解法二:O(nlogk)アルゴリズムは、大量のデータを処理するのに適している.まず、kサイズのデータコンテナに最小のk個の数字を格納し、入力したn個の整数から1個の数を読み込むたびに、コンテナに既存の数字がk個未満であれば、その数を直接コンテナに入れることができます.コンテナにk個の数字がある場合、すなわちコンテナがいっぱいである場合、既存のk個の数の最大値を見つけ、今回挿入する整数と最大値を比較し、挿入する値が現在の最大値より小さい場合、この数で既存の最大値を置き換えます.毎回k個の整数の中の最大数を見つける必要があるため、最大数で完成することができ、最上位ではルートノードの値は常にそのサブツリーの中の任意のノードの値より大きいので、毎回O(1)で既存のk個の数値の最大値を得ることができ、O(lonk)は削除と挿入操作を完成する.(コードはingを理解しており、その後更新されます)