[数据结构与算法]leetcode-最小的k个数

一.题目描述

输入整数数组?arr?，找出其中最小的?k?个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

二.代码

    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        helper(arr, 0, arr.length - 1, k);
        return Arrays.copyOf(arr, k);
    }

    public void helper(int[] arr, int left, int right, int k) {
        if (left >= right) {
            return;
        }
        int pivot = arr[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        arr[left] = arr[i];
        arr[i] = pivot;
        if (i == k) {
            return;
        } else if (i > k) {
            helper(arr, left, i - 1, k);
        } else {
            helper(arr, i + 1, right, k);
        }
    }