复习 - JZ29 最小的K个数

因为是最小的k个数 但是数组从零开始算 所以应该是index最小为k-1的数
快排思想

import java.util.ArrayList;

public class Solution {
    int target = -1;
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        partitoin(input,0,input.length-1,k-1);

        for(int i=0; i<input.length && k>0; i++) {
            if(input[i] <= target) {res.add(input[i]); k--;}
        }
        return res;
    }

    public void partitoin(int [] nums, int l, int r, int k){
        if(l>r) return;
        int i = l;
        int j = r;
        int temp = nums[l];

        while(i<j){
            while(i<j && nums[j]>=nums[l]) j--;
            while(i<j && nums[l]>=nums[i]) i++;
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        nums[i] = nums[l];
        nums[l] = temp;

        if(i == k) target = nums[i];
        else if(i>k) partitoin(nums,l,i-1,k);
        else partitoin(nums,i+1,r,k);        
    }
}