Получите количество конфликтов между двумя массивами [Divide and Conquer]

Question

В настоящее время я работаю над проектом, который связан с получением количества конфликтов между двумя массивами. Это означает различия в порядке, в которых определенные числа помещаются в массив. Каждый номер появляется только один раз, и два массива всегда имеют одинаковый размер.

Например:

[1,2,3,4] 
[4,3,2,1] 

Эти два массива имеют 6 конфликтов:

• 1 приходит 2 в первом массиве, но 2 приходит на 1 в секунду, так что конфликт + 1.
• 1 приходит 3 в первом массиве, но 3 приходит на 1 в секунду, так что конфликт + 1.
• т.д.

Я пробовал некоторые подходы к созданию алгоритма, который вычисляет сумму в O (n log n). Я уже сделал это с помощью динамического программирования, которое является O (N²), но мне нужен алгоритм, который вычисляет значение Divide и Conquer.

У любого человека есть мысливые мысли.

Answer 1

Вы также можете использовать self balancing binary search tree для нахождения количества конфликтов («инверсии»). Например, возьмите AVL tree.

Initialize inversion count = 0.

Iterate из 0 to n-1 и сделайте следующее для каждого arr[i]

Вставка также обновляет результат. Продолжайте считать число больших узлов, когда дерево проходит от корня до листа.

Когда мы вставляем arr [i], элементы из arr [0] в arr [i-1] уже вставлены в AVL Tree. Все, что нам нужно сделать, - это подсчет этих узлов. Для вставки в дерево AVL мы пересекаем дерево от корня до листа, сравнивая каждый узел с arr [i [].

Когда arr [i [меньше текущего узла, мы увеличиваем количество инверсий на 1 плюс число узлов в правом поддереве текущего узла. Это в основном подсчет больших элементов слева от arr [i], т. Е. Инверсий.

Временная сложность указанного раствора O(n Log n), как AVL вставка занимает O(Log n) time.