Найти K-ое наибольшее число за один проход без сохранения всего массива

Question

Алгоритм, который я имею в виду:

• сохранить MaxHeap размера K
• вставить каждый элемент
• пропустить меньшее значение, если куча заполнена
• В конце концов, Kth max является меньшим из MaxHeap

Это даст мне O (NlogK).Есть ли лучший алгоритм?Я не могу сделать быстрый выбор, потому что массив не может быть сохранен в памяти.

Answer 1

В зависимости от ваших ограничений памяти, вы можете использовать модифицированную версию алгоритма медианы медиан для решения проблемы за время O (n) и пространство O (k).

Идея состоит в том, чтоследующим образом.Поддерживать массив размером 2 КБ в памяти.Заполните этот буфер первыми 2k элементами из массива, затем запустите на нем алгоритм медианы медиан, чтобы поместить самые большие k элементов в первой половине массива и наименьшие k элементов во второй половине.Затем откажитесь от наименьших k элементов.Теперь загрузите следующие k элементов во вторую половину массива, используйте алгоритм медианы медиан, чтобы снова поместить верхние k элементов слева и нижние k элементов справа.Если вы проведете этот процесс по всему массиву - заменив вторую половину буфера следующими k элементами из массива, а затем, используя медиану медиан, переместите верхние k из них в левую половину - тогда в конце вы получитеиметь верхние k элементов в левой половине массива.Нахождение наименьшего из них (за O (k) время) даст вам k-й наибольший элемент.

В целом вы в конечном итоге делаете O (n / k) вызовов алгоритма медианы медиан смассив размера O (k), который представляет собой O (n / k), для вызова алгоритма, который занимает время O (k), для чистого времени выполнения O (n).Это, в сочетании с последним этапом, выполняется за O (n + k) = O (n) время.Кроме того, поскольку использование памяти для шага медианы медиан составляет O (k), а поскольку у вас есть буфер размером O (k), он использует только O (k) памяти.Другими словами, это асимптотически быстрее, чем решение с минимальной кучей, и асимптотически эквивалентно в памяти.

Надеюсь, это поможет!

Answer 2

Это известно как http://en.wikipedia.org/wiki/Selection_algorithm

В частности, один алгоритм http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

Это O(N) время и O(1) пространство. Я считаю, что это можно сделать на месте, если ваш массив не отсортирован. Если ваш массив хранится извне (жесткий диск, сеть и т. Д.), Вы можете использовать слова ~K, с которыми вам нужно работать. Если ваш массив динамически генерируется функцией, вы окажетесь в аналогичной ситуации.

Answer 3

У меня есть реализация с PriorityQueue. Попробуйте это:

import java.util.PriorityQueue;

public class FindKthLargestElementWithHeap {

    /**
     * We can use a min heap to solve this problem. 
     * The heap stores the top k elements.
     * Whenever the size is greater than k, delete the min.
     * Time complexity is O(nlog(k)).
     * Space complexity is O(k) for storing the top k numbers.
     */
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>(k);
        for(int i: nums){
            q.offer(i);

            if(q.size()>k){
                q.poll();
            }
        }

        return q.peek();
    }

    public static void main(String args[]) {
        int[] nums = {5,8,6,97,12,3,5,6,4,2,3,};
        //Return the second largest number
        System.out.println(findKthLargest(nums,2));
    }

}

Для получения дополнительной информации, пожалуйста, посетите: https://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/FindKthLargestElementWithHeap.java.

Answer 4

запустил этот код - он работает нормально, не касаясь позиции элемента и не сортируя то же самое.

public class nth {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        calc.getit(2);
    }

}
class calc{
    static int arr[] = { 1, 23, 47, 81, 92, 87, 52, 48, 56, 66, 65, 76, 71, 85,
        49, 53, 56, 61, 65, 84 };

    static void getit(int k){
        int i,j=0;
        for(i=0;i<arr.length;i++){
            int c=0;
            for(j=0;j<arr.length;j++){
                if(arr[i]>arr[j]){
                    c++;
                }
            }
            if(c==k-1){
                System.out.println(arr[i]);
            }
        }
    }
}

Answer 5

Немного измените алгоритм, потому что maxheap не поддерживает эффективный поиск самых маленьких.

• Вставьте первые K предметов в мин-куча

• Для остальных элементов, если значение больше кучи головка

  • выдвиньте голову и вставьте новый предмет.

• Голова является K-м по величине предметом.

Худшим случаем по-прежнему является O (N lg K) для входа, где каждый элемент больше, чем наименьшее из последних K. Но для случайно распределенного входа вам нужно будет только выполнить операцию кучи на меньшем процентное соотношение предметов.