題目：

輸入整數(shù)數(shù)組 arr ，找出其中最小的 k 個數(shù)。例如，輸入 4、5、1、6、2、7、3、8 這 8 個數(shù)字，則最小的 4 個數(shù)字是 1、2、3、4。

示例：

輸入：arr = [3,2,1], k = 2
輸出：[1,2] 或者 [2,1]

輸入：arr = [0,1,2,1], k = 1
輸出：[0]

思考：

• 找到一個數(shù)組中最小的 k 個數(shù)，得出要對該數(shù)組進(jìn)行排序

• 排序算法該如何選擇呢？

• 根據(jù)題目要求，不要求輸出的這 k 個數(shù)的順序，考慮使用快速排序

• 因?yàn)槭禽敵鲎钚〉?k 個數(shù)，索引從 0 開始，所以當(dāng)基準(zhǔn)數(shù)為 k+1 小的數(shù)時，這個基準(zhǔn)數(shù)的左邊子數(shù)組就是我們要找的 k 個數(shù)，也就是基準(zhǔn)數(shù)索引為 k 時

• 使用快速排序劃分子數(shù)組，每劃分一次看基準(zhǔn)數(shù)索引是否等于 k

• 若 k < 基準(zhǔn)數(shù)索引 ，代表第 k+1 小的數(shù)字在 左子數(shù)組 中，則遞歸左子數(shù)組

• 若 k > 基準(zhǔn)數(shù)索引 ，代表第 k+1 小的數(shù)字在 右子數(shù)組 中，則遞歸右子數(shù)組

• 否則直接返回?cái)?shù)組前 k 個數(shù)字

題解：

class Solution {public int[] getLeastNumbers(int[] arr, int k) {if (k >= arr.length) return arr;return quickSort(arr, k, 0, arr.length-1);}private int[] quickSort(int[] arr, int k, int l, int r){int i = l, j = r;while (i<j){while (i<j && arr[j] >= arr[l]) j--;while (i<j && arr[i] <= arr[l]) i++;swap(arr,i,j);}swap(arr,i,l);//基準(zhǔn)數(shù)索引 > k,遞歸左子數(shù)組if (i > k) return quickSort(arr, k, l, i-1);//基準(zhǔn)數(shù)索引 < k,遞歸右子數(shù)組if (i < k) return quickSort(arr, k, i+1, r);return Arrays.copyOf(arr, k);}//交換方法private void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}