题解 | 最小的K个数

import java.util.*;


public class Solution {

    // 使用快速排序
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        // write code here
        if(k > input.length || k == 0) return list;
        quickSort(input,list,k,0,input.length-1);
        return list;
    }

    // 快速排序的思路就是找到一个中间值，我们默认第一个，经过一轮比较之后，大于中枢的都在他后面，小于他的都在他前面。然后判断中枢的位置，如果刚好等于k，那么他前面的k个元素就是我们要找的
    public void quickSort(int[] input, ArrayList<Integer> res, int k, int left, int right){
        int start = left;
        int end = right;
        while(left < right){
            while(left < right && input[right] >= input[start]){
                right--;
            }
            while(left < right && input[left] <= input[start]){
                left++;
            }
            swap(input,left,right);
        }
        swap(input,left,start);
        if(left > k){
            quickSort(input,res,k,start,left - 1);
        }else if(left < k){
            quickSort(input,res,k,left+1,end);
        }else{
            for(int m = 0;m<k;++m){
                res.add(input[m]);
            }
        }
    }

    public void swap(int[] arr, int i, int j){
        if(i == j){
            return;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}