问题

输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

思路

  1. 对数组使用排序算法,然后取其中最小的k个数字即可。
  2. 利用快速排序的思想,每次Partition都会使得Pivot左边的数字小于或等于Pivot的值,即得到了一个数值的集合,该集合满足任取一个数均小于Pivot的值。利用这个特性可以将原问题转化为求某次快排Partition操作后得到的左右指针相遇时的下标值为k-1的情况。
  3. 利用大根堆来实现,设置一个大小为k的大根堆堆,元素小于等于k个时直接放入,大于k个时考虑新元素的大小,若新元素小于该大根堆的堆顶,则去掉堆顶并将新元素放入堆中。
  4. 对数组而言,直接构造一个对应的二叉搜索树然后遍历相应数目的最小值即可。

实现

这里采用思路2来实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr == null || arr.length == 0 || k == 0){
            return new int[0];
        }
        return search(arr, k - 1, 0, arr.length - 1);
    }

    //找到第k小的数对应的下标
    public int[] search(int[] arr, int k, int low, int high){
        int index = partition(arr, k, low, high);
        if (index == k) {
            return Arrays.copyOf(arr, index + 1);
        }
        return index > k ? search(arr, k, low, index - 1) : search(arr, k, index + 1, high);
    }

    public int partition(int[] arr, int k, int left, int right){
        int low = left, high = right;
        int pivot = arr[left];
        while(low < high){
            while(arr[high] >= pivot && low < high){
                high--;
            }
            while(arr[low] <= pivot && low < high){
                low++;
            }
            if(low < high){
                int temp = arr[low];
                arr[low] = arr[high];
                arr[high] = temp;
            }
        }
        arr[left] = arr[low];
        arr[low] = pivot;
        return low;
    }
}