Как найти количество инверсий в массиве? [duplicate]

На этот вопрос уже есть ответы здесь :

Закрыто 7 лет назад .

Возможный дубликат:
Подсчет инверсий в массиве

Это вопрос телефонного интервью : «Найти количество инверсий в массиве». Я предполагаю, что они имеют в виду решение O (N log N). Я считаю, что это не может быть лучше, чем O (N log N), поскольку это сложность сортировки.

Ответы на аналогичный вопрос можно резюмировать следующим образом:

Вычислите половину расстояния, на которое элементы должны быть перемещены для сортировки массива: скопируйте массив и отсортируйте копию. Для каждого элемента исходного массива a [i] найдите его позицию j в отсортированной копии (двоичный поиск) и просуммируйте половинки расстояний abs (i - j) /2 .
Изменить сортировку слиянием : изменить слияние для подсчета инверсий между двумя отсортированными массивами и запустить обычную сортировку слиянием с измененным ] слияние .

Есть ли в этом смысл? Есть ли другие (может быть, более простые) решения? Разве Это слишком сложно для телефонного интервью?

задан Rob 30 November 2017 в 02:52

0 ответов

Другие вопросы по тегам:

arrays algorithm sorting

Как найти количество инверсий в массиве? [duplicate]

0 ответов

Похожие вопросы: