剣指offer最小k個数(java)

剣指offer最小k個数(java)
タイトルの説明
n個の整数を入力し、その中で最も小さいK個の数を見つけます.例えば4,5,1,6,2,7,3,8の8つの数字を入力すると、最小の4つの数字は1,2,3,4であり、
構想解析
partition()メソッドを使用して、配列のk番目の数に基づいて、kより小さい数字が左側にあるように調整します.注釈の詳細な解析
JAvaコード

import java.util.ArrayList;
/*  n   ，       K  。
    4,5,1,6,2,7,3,8 8   ，    4    1,2,3,4,。*/
public class Solution_KLeastNumbers {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //        ，      
        ArrayList<Integer> KLeast = new ArrayList<Integer>();
        //    ，  k    0，  k       ，      ArrayList
        if (input == null || k <= 0 || k > input.length)
            return KLeast;
        
        int left = 0;
        int right = input.length - 1;
        //  partition()      （ left    left）
        int index = partition(input, left, right);
        //      ，    k-1 ,    0   ，      k 
        while (index != k - 1) {
            if (index < k - 1) {
                left = index + 1;
                //            
                index = partition(input,left,right);
            } else {
                right = index - 1;
                index = partition(input,left,right);
            }
        }
        //   k  
        for(int i = 0;i < k; i++)
            KLeast.add(input[i]);
        return KLeast;
    }
    
        private int partition(int[] arr,int left,int right){
                int tempkey = arr[left];
                int temp;
                while(left < right){	//    
                    //      ,    tempkey ，      （right--），         tempkey （while  ）
                    while(left < right && arr[right] >= tempkey)
                        right--;
                    //  
                    temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                    //      ,    tempkey ，      （left++），        tempkey  （while  ）
                    while(left < right && arr[left] <= tempkey)
                        left++;
                    //  
                    temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                }
                //          left    
                return left;
        }
}