题解 | #最小的K个数#

记录

import java.util.*;

public class Solution {
    Random random = new Random();
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        if (k == 0 || k > input.length) {
            return list1;
        }
        int left = 0;
        int right = input.length - 1;
        int k1 = k - 1;
        while (true){
            int temp = quicksort(input, left, right);
            if (temp == k1){
                for (int i = 0; i < k; i++){
                    list1.add(input[i]);
                }
                return list1;
            } else if (temp < k1){
                left = temp + 1;
            } else {
                right = temp - 1;
            }
        }

    }
    public int quicksort(int[] input, int left, int right){
        if (right > left){
            int index = left + 1 + random.nextInt(right - left);
            swap(input, index, left);
        }
        int j = left;
        int privot = input[left];
        for (int i = left + 1; i <= right; i++){
            if (input[i] < privot){
                j++;
                swap(input, i, j);
            }
        }
        swap(input, left, j);
        return j;
    }
    public void swap(int[] input, int i, int j){
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}