leetcode: минимальное число k (одиннадцать)

алгоритм

тема:

Разработайте алгоритм поиска наименьших k чисел в массиве. Верните k чисел в любом порядке.

Пример:

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

class Solution {    public int[] smallestK(int[] arr, int k) {    }}

отвечать:

Используйте метод кучи для решения проблемы:

Мы используем большую корневую кучу, чтобы поддерживать верхние k маленьких значений массива в режиме реального времени. Сначала вставьте первые k чисел в большую корневую кучу, а затем начните обход с числа k + 1. Если текущее пройденное число меньше, чем число в верхней части большой корневой кучи, извлеките число в верхней части куча, а потом вставить текущее количество пройденных. Наконец, сохраните число из большой корневой кучи в массив и верните его. (Поскольку куча (т. е. приоритетная очередь) в языке C++ — это большая корневая куча, мы можем это сделать. А пара в языке Python — это маленькая корневая куча, поэтому нам нужно взять обратное значение всех чисел в Массив для использования маленького корня Небольшое значение k перед обслуживанием кучи Даже если куча в java по умолчанию является небольшой корневой кучей, ее можно вручную заменить большой корневой кучей.

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        for (int i = 0; i < k; ++i) {
            queue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; ++i) {
            if (queue.peek() > arr[i]) {
                queue.poll();//获取但不删除队首元素
                queue.offer(arr[i]);//插入元素并返回false当插入失败
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = queue.poll();获取并删除队首元素，再调整
        }
        return vec;
    }
}

Идеи:

Используя структуру данных большой корневой кучи, первые k уже являются большой корневой кучей, и вам нужно использовать только самое большое, то есть k-е наибольшее число, для сравнения со следующим каждый раз, а финальное первое число k является наименьшим числом k.

Проблема очереди приоритетов в java будет объяснена в следующем блоге!

Категории