【剑指offer】最小的K个数

方法1： 用大根堆维护k个最小值。O(nlogk)

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input == null || k > input.length || k <= 0) {
            return list;
        }
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        for (int i = 0; i < k; i++) {
            queue.add(input[i]);
        }
        for (int i = k; i < input.length; i++) {
            int val = queue.peek();
            if (input[i] < val) {
                queue.remove();
                queue.add(input[i]);
            }
        }
        while (!queue.isEmpty()) {
            list.add(queue.poll());
        }
        return list;
    }
}

方法2： 基于快排算法 --> 求数组总第k大的数字，小的放左，大的放右 O(n)

import java.util.ArrayList;

public class Solution {
    public int Partition(int[] input, int l, int r) {
        int x = input[l];
        while (l < r) {
            while (l < r && input[r] >= x) r--;
            input[l] = input[r];
            while (l < r && input[l] <= x) l++;
            input[r] = input[l];
        }
        input[l] = x;
        return l;
    }

    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input == null || k > input.length || k <= 0) {
            return list;
        }
        int l = 0, r = input.length - 1, mid = -1;
        while (mid != k - 1) {
            mid = Partition(input, l, r);
            if (mid > k - 1) r = mid - 1;
            if (mid < k - 1) l = mid + 1;
        }
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }
        return list;
    }
}