《剑指offer第二版》面试题40：最小的k个数（java）

题目描述

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

解题思路1

• 可以参考面试题39"数组中出现次数超过一半的数字"，使用partation方法来解决这个问题，使得比第k个数字小的所有数字都位于数组左边，比第k个数字大的数字都位于右边。这样位于数组左边的k个数字就是最小的k个数字，但这个k个数字的顺序不一定是排序的。

代码

List<Integer> getLeastNumbers(int[] arrs, int k) {
    if (arrs == null || arrs.length <= 0 || k <= 0 || k > arrs.length) {
        return new ArrayList<>();
    }

    int start = 0;
    int end  = arrs.length - 1;
    int middleIndex = partation(arrs, start, end);
    while (middleIndex != k - 1) {
        if (middleIndex < k - 1) {
            start = middleIndex + 1;
            middleIndex = partation(arrs, start, end);
        } else {
            end = end - 1;
            middleIndex = partation(arrs, start, end);
        }
    }
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < k; i ++) {
        result.add(arrs[i]);
    }
    return result;
}

解题思路2

1. 创建一个容量为k的容器来保存最小的k个数字。
2. 遍历数组，如果容器里的数字不到k个，则将数字放入容器中。
3. 如果容器里的数字等于k个，则找出容器里的最大值，如果该值大于当前遍历的数字，则删除该最大值，将遍历的数字插入容器中。

代码

List<Integer> getLeastNumbers_v2(int[] arrs, int k) {
    if (arrs ==null || arrs.length <= 0 || k <= 0) {
        return new ArrayList<>();
    }
    // 构造优先队列，便于获取队列里的最大值
    Queue<Integer> queue = new PriorityQueue<>(k, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });

    for (int i = 0; i < arrs.length; i++) {
        if (queue.size() < k) {
            // 队列容量未满
            queue.add(arrs[i]);
        } else {
            if (queue.peek() > arrs[i]) {
                // 替换队列里的最大值
                queue.poll();
                queue.add(arrs[i]);
            }
        }
    }

    return new ArrayList<>(queue);
}