一、题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
二、题目分析
- 典型的排序题目，直接使用-快速排序
- 注意一下，input数组的空值和input.length的值与K值的比较
三、题目代码
package offer; import java.util.ArrayList; /* * 最小K个数 */ public class Test28 { static ArrayList<Integer> list = new ArrayList<Integer>(); public static void main(String[] args) { Test28 test28 = new Test28(); int[] input = new int[] { 4, 5, 1, 6, 2, 7, 3, 8 }; list = test28.GetLeastNumbers_Solution(input, 4); System.out.println(list); } public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) { if (input.length == 0 || input.length < k) { return list; } sort(input, 0, input.length - 1); for (int i = 0; i < k; i++) { list.add(input[i]); } return list; } void sort(int[] input, int start, int end) { if (start > end) { return; } int i = start; int j = end; int key = input[i]; while (i < j) { while (i < j && input[j] >= key) { j--; } input[i] = input[j]; while (i < j && input[i] <= key) { i++; } input[j] = input[i]; } input[i] = key; sort(input, start, i - 1); sort(input, i + 1, end); } }
