Извлечение K самых больших элементов из массива из N целых чисел за O (N + K) времени - PullRequest
Новая
       13

Извлечение K самых больших элементов из массива из N целых чисел за O (N + K) времени

4 голосов
/ 01 октября 2019

Итак, у нас есть список из N целых чисел, из которого мы хотим получить K самых больших целых чисел (не отсортированных). Проблема в том, что это должно быть в состоянии работать в O (N + K). Это то, что указано в задании.

Я проверил различные алгоритмы и даже создал свой собственный, но лучшее, что я могу получить, это O ((nk) * k), который, я думаю, не близок к O(N + K), если я не прав.

Существуют ли какие-либо алгоритмы, которые могут сделать это в O (N + K), предполагая, что значения в списке довольно случайные и все положительные? (Мы не знаем максимального значения, которое они могут получить)

Обратите внимание, что мне нужно найти K наибольших целых чисел, как не в K-ом наибольшем, а в N, K целых числах.

Пример: N = 5, K = 2 Вход: 5 6 8 9 3 Выход: 9 8

Ответы [ 2 ]

4 голосов
/ 01 октября 2019

Алгоритм выбора используется для поиска k-го наибольшего элемента. Медиана медиан - это алгоритм выбора O (n).

Следовательно, для вашей задачи существует простой алгоритм O (n): пусть KTH будет k-м наибольшим элементом, возвращаемымВаш алгоритм выбора. Это занимает O (N) время. Сканирование массива и извлечение всех элементов> = KTH. Это занимает O (n) время.

Быстрый выбор - еще один алгоритм выбора, о котором стоит знать. Он основан на быстрой сортировке, поэтому в среднем он равен только O (n).

1 голос
/ 04 октября 2019

Идея состоит в том, чтобы создать дерево двоичного поиска, которое можно сделать в O (log N) , хотя в худшем случае O (N) [где N - этовсего узлов / элементов массива в этом случае].

Теперь мы можем выполнить обход по порядку, чтобы получить все элементы в отсортированном порядке, что можно сделать O (N) [Доказательство: Сложности обходов двоичного дерева ]

Теперь пройдитесь по отсортированным элементам K-раз (в порядке убывания);

Следовательно, общая сложность будет: O (N) + O (N) + O (K) => O (N + K)

ОСУЩЕСТВЛЕНИЕ: 

public class Solution{
static class BST{
    int val;
    BST left, right;

    public BST(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}
// making bst from the array elements
static BST add(BST root, int item) {
    if(root == null) return new BST(item);

    if(root.val > item)
        root.left = add(root.left, item);

    else root.right = add(root.right, item);

    return root;
}
// doing inorder to get all elements in sorted order
static void inorder(BST root, List<Integer> list) {
    if(root.left != null)
        inorder(root.left, list);

    list.add(root.val);

    if(root.right != null)
        inorder(root.right, list);

}
public static void main(String[] args) {
    //Example: N = 5, K = 2 Input: 5 6 8 9 3 Output: 9 8
    int [] a = {1, 9, 2, 7, 3, -1, 0, 5, 11};

    BST root = null;

    for(int i=0; i<a.length; i++) {
        root = add(root, a[i]);
    }
    List<Integer> list = new ArrayList<Integer>();
    inorder(root, list);

   // process the list K times, to get K-th largest elements        
}

NB: в случае дублирующихся значений, вы должны сделать суб-лист для каждого узла!

...