题解 | #最小的K个数#
最小的K个数
https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param input int整型一维数组 * @param k int整型 * @return int整型ArrayList */ public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) { // write code here ArrayList<Integer> list = new ArrayList<>(k); if (input.length < k) { return list; } quickSort(input, 0, input.length - 1); for (int i = 0; i < k; i++) { list.add(input[i]); } return list; } public static void quickSort(int[] arr, int low, int high) { //log.info("arr: {},low:{},high:{}", arr, low, high); if (low < high) { // 找到划分点 int pivotIndex = index(arr, low, high); //log.info("pivotIndex: {},arr:{}", pivotIndex, arr); // 递归地对左右两部分进行快速排序 quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } } private static int index(int[] array, int low, int high) { int idx = array[high]; int i = (low - 1); for (int j = low ; j < high ; j++) { if (idx >= array[j]) { i++; // 移动数据,小于基准值的放在最左面 int temp = array[i]; array[i] = array[j]; array[j] = temp; } } // 本次移动之后,将基准值放入左面 i 之后 int temp = array[i + 1] ; array[i + 1] = array[high]; array[high] = temp; return i + 1; } } 排序后截取数据