Как найти K-й самый большой элемент в подмассиве - PullRequest
Новая
       4

Как найти K-й самый большой элемент в подмассиве

0 голосов
/ 11 октября 2019

Я хочу иметь возможность найти K-й по величине элемент / элемент в подмассиве.

Например: список: 3 15 19 7 14 нижняя граница: 2 верхняя граница: 4 K: 2

Программа выдаст 15

Пример 2: список: 3 15 19 7 14 нижняя граница: 1 верхняя граница: 2 K: 2

Программа выдаст 3

То, что я до сих пор делал, это цикл по самому подмассиву. Затем я сохранил отсортированный подмассив в другом массиве и оттуда нашел N-й по величине элемент. 

int l = 4
int r = 2
int k = 2
int[] temp = new int[1+r-l];
for(int j = l-1; j < r; j++) {
    temp[j-l+1] = arr[j];
}
Arrays.sort(temp);
System.out.println(temp[temp.length-k]);

Я считаю, что есть гораздо более быстрый способ решения этой проблемы.

1 Ответ

0 голосов
/ 12 октября 2019

Я могу придумать 3 возможных решения:

1. Сортировка

Это решение, которое вы дали. Временная сложность будет O (n * log (n)) , где n - количество элементов между нижней границей и верхней границей.

2. Куча

Совершенно аналогично первому решению, но это немного уменьшит временную сложность. Весь смысл в том, чтобы создать приоритетную очередь и добавить элементы из нижней границы в верхнюю, сохраняя при этом размер очереди приоритета как K. Когда размер переполняется, просто удалите из очереди самый маленький элемент. Тогда в очереди с приоритетами останется K самых больших элементов в пределах границ. Опрос наименьшего элемента из этой приоритетной очереди даст Kth наибольший элемент. Сложность по времени будет O (n * log (k)) , поскольку опрос занимает время log (k) из-за поддерживаемого размера K. 

    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    for (int j = l-1; j < r; j++) {
        pq.add(arr[j]);
        if (pq.size() > k) pq.poll();
    }
    System.out.println(pq.poll());

3. Быстрый выбор

Это известно как Алгоритм выделения Хоара , очень похожий на быструю сортировку. Временная сложность будет в среднем O (n) , но в худшем случае O (n ^ 2) . Вот страница Википедии, на которую вы можете сослаться: https://en.wikipedia.org/wiki/Quickselect

...