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

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

Числа называются "обратными упорядоченными", если N [i] > N [j] для я < к. Например, в списке: 3 4 1 6 7 3, обратные упорядоченные элементы: (3,1) (4,1) (4,3) (6,3) (7,3).

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

Ответ 1

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

Ответ 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)

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

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

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

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

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

куча (3) item (7)

Выход (7, 3)

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

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

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

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

куча (1, 3, 6, 7) пункт (4)

найти и найти 3 и 1. выход (4, 3) (4, 1)

и т.д....

Изменить, возможно на самом деле

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

Ответ 3

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

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

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

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

Ответ 4

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

Ответ 5

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