【剑指Offer】最小的K个数

题目

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

O(n)的算法，只有当我们可以修改输入的数组时可用

public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
    ArrayList<Integer> result = new ArrayList<>();

    if (input == null || input.length <= 0 || k > input.length || k < 1)
        return result;

    int left = 0;
    int right = input.length - 1;

    int pivot = Partition(input, left, right);

    while (pivot != k - 1) {
        if (pivot < k - 1) {
            left = pivot + 1;
            pivot = Partition(input, left, right);
        } else {
            right = pivot - 1;
            pivot = Partition(input, left, right);
        }
    }

    for (int i = 0; i < k; i++)
        result.add(input[i]);

    return result;
}

private int Partition(int[] array, int start, int end){
    int i = start + 1;

    for (int j = start + 1; j <= end; j++){
        if (array[j] < array[start]) {
            Swap(array, i, j);
            i++;
        }
    }

    Swap(array, start, --i);

    return i;
}

private void Swap(int[] array, int i, int j){
    if (i == j)
        return;

    array[i] = array[i] ^ array[j];
    array[j] = array[i] ^ array[j];
    array[i] = array[j] ^ array[i];
}

O(nlogk)的算法，特别适合处理海量数据

public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
    ArrayList<Integer> result = new ArrayList<>();

    if (input == null || input.length <= 0 || k > input.length || k < 1)
        return result;

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });

    for (int i = 0; i < input.length; i++) {
        if (maxHeap.size() < k)
            maxHeap.offer(input[i]);
        else if (input[i] < maxHeap.peek()) {
            maxHeap.poll();
            maxHeap.offer(input[i]);
        }
    }

    for (Integer i : maxHeap)
        result.add(i);

    return result;
}