题目描述

  • 输入n个整数，找出其中最小的K个数。
  • 例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

解法1

  • 对数组排序，取前边k个数存到list集合中
  • 该解法时间复杂度依赖于排序

代码实现

  1. public ArrayList<Integer> getLeastNumbers(int [] input, int k) {
  3.     ArrayList<Integer> list = new ArrayList<Integer>();
  4.     if(input == null || input.length == 0 || input.length < k || k <= 0){
  5.         return list;
  6.     }
  7.     Arrays.sort(input);
  8.     for(int i = 0; i < k; i++){
  9.         list.add(input[i]);
  10.     }
  11.     return list;
  12. }

解法2

  • 基于partition函数
  • 只有当我们可以修改输入的数组时可用

代码实现

  1. public ArrayList<Integer> GetLeastNumbers_Solution2(int [] input, int k) {
  3.     ArrayList<Integer> list = new ArrayList<Integer>();
  4.     if(input == null || input.length == 0 || input.length < k || k <= 0){
  5.         return list;
  6.     }
  7.     int start = 0;
  8.     int end = input.length - 1;
  9.     int index = partition(input, start, end);
  10.     while(index != k - 1){
  11.         if(index > k - 1){
  12.             end = index - 1;
  13.             index = partition(input, start, end);
  14.         }else{
  15.             start = index + 1;
  16.             index = partition(input, start, end);
  17.         }
  18.     }
  19.     for(int i = 0; i < k; i++){
  20.         list.add(input[i]);
  21.     }
  22.     return list;
  23. }
  24. private int partition(int[] input, int low, int high) {
  25.     int pivotKey = input[low];
  26.     while(low < high){
  27.         while(low < high && input[high] >= pivotKey){
  28.             high--;
  29.         }
  30.         input[low] = input[high];
  31.         while(low < high && input[low] <= pivotKey){
  32.             low++;
  33.         }
  34.         input[high] = input[low];
  35.     }
  36.     input[low] = pivotKey;
  37.     return low;
  38. }

解法3

  • 适合海量数据的处理
  • 创建一个用于保存最小k个数的容器
  • 第一步是放入k个元素，
  • 第二步是比较容器中最大的数与当前数组遍历的那个数的大小
  • 如果容器中最大的数比当前遍历的数大，就移除该数，并放入当前遍历的那个数
  • 最大堆或红黑树都能实现这样的容器

代码实现

  1. public ArrayList<Integer> GetLeastNumbers_Solution3(int[] input, int k) {
  2.     ArrayList<Integer> list = new ArrayList<Integer>();
  3.     if(input == null || input.length == 0 || input.length < k || k <= 0){
  4.         return list;
  5.     }
  6.     TreeSet<Integer> s = new TreeSet<Integer>();
  7.     for(int i = 0; i < input.length; i++){
  8.         if(s.size() < k){
  9.             s.add(input[i]);
  10.         }else{
  11.             if(input[i] < s.last()){
  12.                 s.remove(s.last());
  13.                 s.add(input[i]);
  14.             }
  15.         }
  16.     }
  17.     Iterator<Integer> it = s.iterator();
  18.     while(it.hasNext()){
  19.         list.add(it.next());
  20.     }
  21.     return list;
  22. }