个体户网站备案,互联网 现代农业网站建设,福州设计公司排行,wordpress迁移跳转原网站题目#xff1a;
输入整数数组 arr #xff0c;找出其中最小的 k 个数。例如#xff0c;输入 4、5、1、6、2、7、3、8 这 8 个数字#xff0c;则最小的 4 个数字是 1、2、3、4。
示例#xff1a; 输入#xff1a;arr [3,2,1], k 2 输出#xff1a;[1,2] 或者 [2,1] …题目
输入整数数组 arr 找出其中最小的 k 个数。例如输入 4、5、1、6、2、7、3、8 这 8 个数字则最小的 4 个数字是 1、2、3、4。
示例 输入arr [3,2,1], k 2 输出[1,2] 或者 [2,1] 输入arr [0,1,2,1], k 1 输出[0] 思考 找到一个数组中最小的 k 个数得出要对该数组进行排序 排序算法该如何选择呢 根据题目要求不要求输出的这 k 个数的顺序考虑使用快速排序 因为是输出最小的 k 个数索引从 0 开始所以当基准数为 k1 小的数时这个基准数的左边子数组就是我们要找的 k 个数也就是基准数索引为 k 时 使用快速排序划分子数组每划分一次看基准数索引是否等于 k 若 k 基准数索引 代表第 k1 小的数字在 左子数组 中则递归左子数组 若 k 基准数索引 代表第 k1 小的数字在 右子数组 中则递归右子数组 否则直接返回数组前 k 个数字
题解
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 (ij){while (ij arr[j] arr[l]) j--;while (ij arr[i] arr[l]) i;swap(arr,i,j);}swap(arr,i,l);//基准数索引 k,递归左子数组if (i k) return quickSort(arr, k, l, i-1);//基准数索引 k,递归右子数组if (i k) return quickSort(arr, k, i1, 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;}
}
