Интервью Вопрос: Обратные пары

Question

Я получил это для моего интервью:

Числа называются «в обратном порядке», если N [i]> N [j] для i

Как получить количество пар предметов в обратном порядке за время O (nlogn).

Answer 1

Это можно сделать за O (n log n), используя модифицированную версию сортировки слиянием. Делайте деление как обычно, но вы можете считать инверсии при слиянии. Каждый раз, когда вы выбираете элемент из правого списка поверх элемента из левого списка, увеличивается число инверсий на количество элементов, оставшихся в левом списке. Таким образом, на каждом уровне количество инверсий - это количество инверсий, найденных во время слияния, плюс инверсий, найденных каждым рекурсивным вызовом.

Answer 2

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

В общем случае это невозможно .Рассмотрим список:

n, n-1, n-2 ... 4, 3, 2, 1

Пары будут:

(n, n-1), (n, n-2) ... (n, 2), (n, 1), (n-1, n-2), (n-1, n-3) ... ... (3, 2), (3, 1), (2, 1)

Следовательно, существует O (n ^ 2) пар и, следовательно, список не может быть построен в O (n log n)

Однако вы можете сделать это с помощью одного прохода списка :

1. начинаться с конца списка и работать с обратными словами.
2. в то время какперемещение по списку поддерживает кучу чисел, которые вы видели (это приведет к тому, что цикл будет равен O (n log n))
3. для любого числа, с которым вы столкнетесь, выполните поиск в куче, чтобы найти все числа, которыеменьше номера, на котором вы сейчас находитесь.Выведите текущее число и число в куче в виде пары.(это O (n log n), чтобы найти первое совпадение в куче, но будет O (n), чтобы найти все меньшие числа)

Для вашего примера :

Список: 3 4 1 6 7 3

начиная со второго элемента

куча (3) элемент (7)

Выход (7,3)

куча (3, 7) предмета (6)

поиск и поиск 7, вывод (6, 3)

куча (3, 6, 7) предмета(1)

искать и ничего не находить

куча (1, 3, 6, 7) item (4)

искать и находить 3 и 1. выходные данные (4,3) (4, 1)

и т. Д. *

Редактировать, это возможно на самом деле

Поскольку JoshD правильно заметил, что мы ищемдля количества элементов вы можете использовать B-дерево вместо кучи, а затем вы можете получить только количество элементов меньше текущего элемента и добавить его в счетчик.

Answer 3

Как указывает @ jlewis42, вы можете использовать модифицированную версию сортировки слиянием. Я просто хотел добавить, что вы можете использовать любой из стандартных алгоритмов сортировки сравнения , если время наихудшего времени выполнения равно n log n, "оснастив" его подсчетом инверсий во время работы. Смотри также это возле дупе.

Answer 4

Обход справа налево, красно-черное дерево, где каждый узел увеличивается на размер соответствующего поддерева. Таким образом, требуется O (logn), чтобы найти количество элементов ниже заданного.

Answer 5

Эту проблему можно решить, создав двоичное дерево поиска, в котором каждый узел содержит размер своего левого поддерева.

Значения добавляются в BST в обратном порядке исходного массива. Сумма сохраняется, и каждый раз, когда мы идем направо при добавлении узла, текущий сравниваемый узел имеет размер левого поддерева + 1, добавляемый к окончательной сумме (поскольку добавляемое значение больше, чем этот узел и каждое значение в его левом поддерево).

Построение дерева является nlogn, и как только дерево будет построено, сумма будет количеством пар.

Специальная обработка должна быть добавлена ​​для дублирующих номеров в зависимости от требований (то есть, если (4,3) появляется дважды, если он учитывается дважды)