Поиск самых больших чисел K в несортированном массиве

Я пытаюсь найти самые большие числа K с учетом отсортированного массива.

пример: ввод -> [ 5, 12, 45, 32, 9, 20, 15] вывод -> K = 3, [45, 32, 20]

Код, который я написал до сих пор, возвращает самый большой элемент K, но он должен возвращать самые большие числа K. Любая помощь будет оценена по достоинству.

public static int max_Numbers(int [] p, int K, int firstNum, int lastNum)
    {
        int pivot = partitionArr(p, firstNum, lastNum);
        int m = p.length - K;
        if (m == pivot)
        {
            return p[pivot];
        }
        if(m > pivot)
        {
            return max_Numbers(p, K, pivot + 1, lastNum);

        }
        else
        {
            return max_Numbers(p, K, firstNum, pivot - 1);
        }
    }

person user11082882    schedule 17.03.2019    source источник
comment
Если эффективность не важна, просто отсортируйте ее и вернитесь наверх k   -  person Mitch    schedule 17.03.2019
comment
Среднее время работы должно быть O(n)   -  person user11082882    schedule 17.03.2019
comment
Является ли O (n log k) также приемлемым?   -  person Nico Schertler    schedule 17.03.2019
comment
Прочтите stackoverflow.com/questions/19227698/.   -  person Stephen C    schedule 17.03.2019
comment
Проблема, над которой я работаю, требует, чтобы она была O (n).   -  person user11082882    schedule 17.03.2019
comment
Кроме того, обратите внимание, что ваш вопрос может быть закрыт как слишком широкий (поскольку это вопрос, пожалуйста, помогите мне, а не правильный вопрос) и не по теме (поскольку это, по-видимому, запрос на помощь в отладке без надлежащего MCVE)   -  person Stephen C    schedule 17.03.2019
comment
O(N) решения нет. Существует O(NlogK) решение. Убедитесь, что вы поняли проблему. (Подсказка: если вы подставите определенное значение для K, это сделает проблему с решением O(N).)   -  person Stephen C    schedule 17.03.2019
comment
@stephenC: нигде не говорится, что числа нужно возвращать по порядку, хотя вы можете быть правы в том, что это как-то неявно.   -  person rici    schedule 17.03.2019
comment
@rici - Вопрос, на который я ссылался, не указывает, что элементы K должны быть доставлены по порядку. Кажется, я не упомянул заказ...   -  person Stephen C    schedule 17.03.2019
comment
@ user11082882 — Если вам нужно хорошо написанное объяснение, прочитайте baeldung.com/java-kth -самый большой-элемент   -  person Stephen C    schedule 17.03.2019
comment
@stephenc: я не смотрел на вопрос, на который вы ссылались, но решение проблемы разделения O (n) - это известный. Но это линейно только в том случае, если вам не нужно сортировать раздел (или, как вы говорите, k считается постоянным).   -  person rici    schedule 17.03.2019
comment
(QuickSelect с разбиением по медианам медиан на практике неэффективен. Но гарантируется O(n).)   -  person rici    schedule 17.03.2019
comment
@rici, как вы решаете, что пивот будет использовать этот алгоритм?   -  person Msk    schedule 17.03.2019
comment
@msk: как описано в связанной статье в Википедии, вы вычисляете медиану медиан, что дает вам гарантированный непатологический поворот. Вы можете вычислить медиану медиан в O (n).   -  person rici    schedule 17.03.2019
comment
Если массив уже отсортирован, вы возвращаете подмассив, начиная с индекса N-K. Что мне не хватает?   -  person selbie    schedule 17.03.2019


Ответы (2)


Используя ваш отсортированный массив,

for(int i=array.length-1; i>=0 && array.length-1 - i < K; i--) System.out.println(array[i]));
person FailingCoder    schedule 17.03.2019

Одно из свойств используемого вами свода и разбиения заключается в том, что после каждого шага разбиения гарантируется, что все элементы до поворота будут меньше или равны, чем опорный элемент, а все элементы после него будут больше. Таким образом, после того, как вы найдете опорную точку, которая является K-й, в массиве будет самая большая после нее K.

person Javier Cano    schedule 17.03.2019