算法思路
题目要求数组中最小的K个数,很明显我们可以先对数组进行从小到大排序,然后输出前K个数即可;排序算法介绍参考#排序#,这里我们选择快速排序来实现。
算法实现
public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { quickSort(input, 0, input.length - 1); ArrayList<Integer> result = new ArrayList<>(); for (int i = 0; i < k; i++) { result.add(input[i]); } return result; } // 快速排序算法实现 private void quickSort(int[] A, int p, int r) { if (p < r) { int q = partition(A, p, r); quickSort(A, p, q - 1); quickSort(A, q + 1, r); } } private int partition(int[] A, int p, int r) { int x = A[r]; int i = p - 1; for (int j = p; j < r; j++) { if (A[j] <= x) { swap(A, ++i, j); } } swap(A, i + 1, r); return i + 1; } private void swap(int[] A, int i, int j) { if (A[i] != A[j]) { A[i] ^= A[j]; A[j] ^= A[i]; A[i] ^= A[j]; } } }