[剣指Offer]最小のK個数(Java)

   K   -- newcoder   Offer 29

  n   ，       K  。  
  4,5,1,6,2,7,3,8 8   ，    4    1,2,3,4,。

  1：
 * 1、     ，     K    
 * 2、    ，                 ，        

  2：
 * 1、    ，N    ， base    base   
 * 2、 base    k-1 ，          input[k]，       input[k]
 * 3、      k    

package com.codinginterviews.array;

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

/**
 *   ：
 *    K   -- newcoder   Offer 29
 *  
 *     ：
 *   n   ，       K  。    4,5,1,6,2,7,3,8 8   ，    4    1,2,3,4,。 
 */
public class LeastKNumbers
{   
	/**
	 *   ： 
	 * 1、     ，     K    
	 * 2、    ，                 ，        
	 */
    public ArrayList getLeastNumbers_Solution(int [] input, int k) {
        ArrayList ret = new ArrayList<>();
        if (input == null || k == 0) {
            return ret; 
        }
        
        int len = input.length;
        if (len < k) {
            return ret;
        }
        
        //      
        PriorityQueue maxHeap = new PriorityQueue<>(k, new Comparator(){

            @Override
            public int compare(Integer o1, Integer o2)
            {
                return o2 - o1;
            }
            
        });
        
        //     ，                
        for (int i=0; i curVal) {
        			maxHeap.poll();
        			maxHeap.add(curVal);
        		}
        	}
        }
        
        //              list 
        ret.addAll(maxHeap);
        
        return ret;
    }

    /**
     *   ： 
     * 1、    ，N    ， base    base   
     * 2、 base    k-1 ，          input[k]，       input[k]
     * 3、      k    
     */
    public ArrayList getLeastNumbers_SolutionII(int [] input, int k) {
    	ArrayList ret = new ArrayList<>();
    	if (input == null || k == 0) {
    		return ret;
    	}
    	
        int len = input.length;
        
        if (len < k) {
            return ret;
        }
        
        //     ，mid      input[mid]
    	int start = 0;
    	int end = len-1;
    	int mid = getMid(input, 0, len-1);
    	
    	//     ,     k     ，  k         ， k   ，    
    	int targetIdx = k - 1;
    	
        while (mid != targetIdx) {
        	//     mid  
        	if (mid > targetIdx) {
        		end = mid-1;
            //     mid          		
        	} else {
        		start = mid+1;
        	}
    		mid = getMid(input, start, end);
        }
        
        for (int i=0; i<=targetIdx; i++) {
        	ret.add(input[i]);
        }
        
    	return ret;
    }
    
    //  arr[begin]   ，         ，         ，   arr[begin]   
    private int getMid(int[] input, int begin, int end) {
    	//     input[begin]
    	int base = input[begin];
    	
    	//       ，          
    	while (begin < end) {
    		//         base   
    		while (begin=base) {
    			end--;
    		}
    		input[begin] = input[end];
    		
    		//         base   
    		while (begin