Вопрос из интервью: Найдите K-й по величине элемент (topK) [расширенная версия]

алгоритм


Алгоритм E добавлен на исходной основе.

Введение

Это похоже на задачу Top (K), что это значит?Как найти самый большой (K)-й элемент в неупорядоченном массиве?Мы не рассматриваем здесь массивные данные, которые можно загрузить в память.

Во-вторых, обычный алгоритм

Алгоритм А:

Отсортируйте элементы в массиве в порядке возрастания и найдите элемент с индексом k-1 массива. Это самый простой способ для всех. Если вы используете простой алгоритм сортировки,Временная сложность O(n^2).

Алгоритм Б:

  1. первый шаг:Инициализировать массив длиной K, сначала прочитать по K элементов, отсортировать элементы по убыванию (возможен и по возрастанию), при этом K-й по величине элемент является последним.
  2. Шаг 2:Прочитайте следующий элемент и сравните его с отсортированным K-м по величине элементом.Если он больше, удалите текущий K-й по величине элемент и поместите этот элемент в первую K-1 правильную позицию (здесь простоСортировка вставками. Друзья, которые не понимают сортировку вставками, могут посмотреть здесьСортировка графическим выбором и сортировка вставками).
  3. временная сложность:Первый шаг использует общий алгоритм сортировки, а временная сложность O(k^2); второй шаг: (N-k)*(k-1) = Nk-k^2+k. Итак, алгоритм БВременная сложность O(NK).Когда k=N/2 (округление вниз), временная сложность по-прежнему O(n^2).

На самом деле, чтобы найти K-ю большую проблему, вы также можете ее отрицать, то есть найти N-k+1-ю малую проблему. Это эквивалентно.Итак, когда К=N/2, самая сложная часть, но и очень интересная, на этот разЗначение, соответствующее K, является медианой.

В-третьих, лучший алгоритм

Алгоритм С:

  1. Алгоритмическое мышление: прочитать данные в массив, выполнить buildHeap над массивом (здесь мы строим большую верхнюю кучу), а затем выполнить K операций deleteMax над кучей, и результатом K-го раза будет нужное нам значение. (Поскольку это большая верхняя куча, данные сортируются от большего к меньшему, а сортировка кучи будет подробно описана позже).

  2. Теперь давайте решим задачи, оставшиеся от предыдущего раздела,Почему buildHeap линейный?Если вы не знакомы с кучами, вы можете взглянутьГрафическая приоритетная очередь (куча). Давайте сначала посмотрим на реализацию кода.

    public PriorityQueue(T[] items) {
           //当前堆中的元素个数
           currentSize = items.length;
           //可自行实现声明
           array = (T[]) new Comparable[currentSize +1];
           int i = 1;
           for (T item : items){
               array[i++] = item;
           }
           buildHeap();
       }

    private void buildHeap() {
           for (int i = currentSize / 2; i > 0; i--){
               //堆的下滤方法，可参考上面的链接
               percolateDown(i);
           }
       }

На рисунке инициализировано неупорядоченное дерево После 7 percolateDowns получается большая верхняя куча. Как видно из рисунка, имеется 9 пунктирных линий, каждая из которых соответствует 2 сравнениям, всего 18 сравнений. Чтобы определить ограничение по времени для buildHeap, нам нужно посчитатьколичество пунктирных линий, который можно вычислить, вычислив кучувысота всех узлов иполучить,Это максимальное количество пунктирных линий. Сумма равна O(N).

Теорема: содержит 2h+1Сумма высот узлов идеального бинарного дерева (полного бинарного дерева) из -1 узла и высоты h равна 2h+1-1-(ч+1).

  1. Что такое полное бинарное дерево?Полное бинарное дерево — это бинарное дерево, которое полностью заполнено, и последний слой заполнен, как показано на рисунке. Полное бинарное дерево заполняется за исключением последнего слоя, и последний слой также должен быть заполнен слева направо, что является структурой кучи, упомянутой в предыдущей статье. Полное бинарное дерево должно быть полным бинарным деревом, а полное бинарное дерево не обязательно является полным бинарным деревом.

  2. Докажите теорему:

    Легко видеть, что в полном бинарном дереве есть 1 узел на высоте h, 2 узла на высоте h-1, 2^2 узла на высоте h-2 и 2 узла на высоте h-i.iсостоит из узлов.

Умножьте обе части уравнения на 2, чтобы получить:

Вычтите две формулы, чтобы получить:

Итак, теорема доказана.Поскольку куча состоит из полного бинарного дерева, количество узлов в куче равно 2.hи 2h+1между, значит, эта сумма равна O(N).Итак, buildHeap является линейным. Таким образом, временная сложность алгоритма C равна: инициализация массива — O(N), buildHeap — O(N), а для K раз deleeMax требуется O(klogN), поэтомуобщая временная сложностьДа: O(N+N+klogN)=O(N+klogN),Если K равно N/2, время выполнения равно O(NlogN)..

Алгоритм Д:

  1. Идея алгоритма:Мы принимаем идею алгоритма B, но здесь мы строим небольшую верхнюю кучу с узлами K. Пока следующее число больше, чем корневой узел, корневой узел удаляется, а число фильтруется вниз. Следовательно, окончательное K-е наибольшее число алгоритма является номером корневого узла.
  2. временная сложность:Требуется O(k) для построения кучи для номеров K. В худшем случае предполагается, что оставшиеся N-k чисел должны войти в кучу для операции нижней фильтрации.Всего требуется O(k+(N-k)logk). Если K равно N/2, то требуется O(NlogN).

Алгоритм E: быстрый выбор

Ссылаться наБыстрая сортировка и ее оптимизация, используя идею быстрой сортировки, с небольшим изменением.

  • Идея алгоритма:
  1. Если количество элементов в S равно 1, то k=1 и вернуть элементы в S. Если используется метод отсечения для небольших массивов и |S|
  2. Выберите элемент v в S и назовите его точкой опоры;
  3. Разделите S-{v} (остальные элементы в S, кроме опорного элемента) на два непересекающихся множества S1и С2, С1Все элементы в наборе меньше или равны опорному элементу v, S2Все элементы больше или равны опорному элементу;
  4. если k1|, то k-й наибольший элемент должен находиться в S1середина. В этот момент мы возвращаемся к quickSelect(S1, к). Если k=1+|S1|, то опорный элемент является k-м по величине элементом, и мы напрямую возвращаем опорный элемент. В противном случае k-й наибольший элемент должен находиться в S2, это с2(к-|С1|-1) максимальный элемент. Мы делаем рекурсивный вызов и возвращаем quickSelect(S2, к-|S1|-1).
  • Java-реализация:
public class QuickSelect {
    /**
     * 截止范围
     */
    private static final int CUTOFF = 5;

    public static void main(String[] args) {
        Integer[] a = {8, 1, 4, 9, 6, 3, 5, 2, 7, 0, 12, 11, 15, 14, 13, 20, 18, 19, 17, 16};
        int k = 5;
        quickSelect(a, a.length - k + 1);
        System.out.println("第" + k + "大元素是：" + a[a.length - k]);
    }

    public static <T extends Comparable<? super T>> void quickSelect(T[] a, int k) {
        quickSelect(a, 0, a.length - 1, k);
    }

    private static <T extends Comparable<? super T>> void quickSelect(T[] a, int left, int right, int k) {
        if (left + CUTOFF <= right) {
            //三数中值分割法获取枢纽元
            T pivot = median3(a, left, right);

            //开始分割序列
            int i = left, j = right - 1;
            for (; ; ) {
                while (a[++i].compareTo(pivot) < 0) {
                }
                while (a[--j].compareTo(pivot) > 0) {
                }
                if (i < j) {
                    swapReferences(a, i, j);
                } else {
                    break;
                }
            }
            //将枢纽元与位置i的元素交换位置
            swapReferences(a, i, right - 1);

            if (k <= i) {
                quickSelect(a, left, i - 1, k);
            } else if (k > i + 1) {
                quickSelect(a, i + 1, right, k);
            }
        } else {
            insertionSort(a, left, right);
        }
    }

    private static <T extends Comparable<? super T>> T median3(T[] a, int left, int right) {
        int center = (left + right) / 2;
        if (a[center].compareTo(a[left]) < 0) {

            swapReferences(a, left, center);
        }
        if (a[right].compareTo(a[left]) < 0) {
            swapReferences(a, left, right);
        }
        if (a[right].compareTo(a[center]) < 0) {
            swapReferences(a, center, right);
        }
        // 将枢纽元放置到right-1位置
        swapReferences(a, center, right - 1);
        return a[right - 1];
    }

    public static <T> void swapReferences(T[] a, int index1, int index2) {
        T tmp = a[index1];
        a[index1] = a[index2];
        a[index2] = tmp;
    }

    private static <T extends Comparable<? super T>> void insertionSort(T[] a, int left, int right) {
        for (int p = left + 1; p <= right; p++) {
            T tmp = a[p];
            int j;

            for (j = p; j > left && tmp.compareTo(a[j - 1]) < 0; j--) {
                a[j] = a[j - 1];
            }

            a[j] = tmp;
        }
    }
}

//输出结果
//第5大元素是：16

Поскольку здесь я сортирую в порядке возрастания, найти K-е по величине то же самое, что найти N-k+1-е.

  • Худшая временная сложность:Как и в случае с быстрой сортировкой, когда подпоследовательность пуста, наихудшим является O(N2).
  • Средняя временная сложность:Как можно видеть,Быстрый выбор использует рекурсию только по одной подпоследовательности за раз. Средняя временная сложность O(N).

4. Резюме

В этой статье подробно описаны несколько решений задачи top(K): первые два очень обычные, а последние два лучше.Временно дано, что нахождение медианы занимает время O(NlogN).Использование метода быстрого выбора вводится позже, и одновременно рекурсивно используется только одна подпоследовательность, что позволяет достичьСредняя временная сложность O(N).

Категории