题目描述
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例
思路
方法1 采用未改进的快速排序
class Solution {public int[] getLeastNumbers(int[] arr, int k) {int l = 0, r = arr.length - 1;quickSort(arr, l, r);return Arrays.copyOf(arr, k);}void quickSort(int[] arr, int l, int r) {if(l >= r) return;int i = l - 1, j = r + 1, x = arr[l + r >> 1];while(i < j) {do i++; while(arr[i] < x);do j--; while(arr[j] > x);if(i < j) swap(arr, i, j); }quickSort(arr, l, j);quickSort(arr, j + 1, r); }void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}
}
