Измерение того, насколько «не в порядке» массив

Question

Учитывая массив значений, я хочу найти общую «оценку», где оценка каждого элемента - это число элементов с меньшим значением, которые встречаются перед ним в массиве.

например

values: 4 1 3 2 5
scores: 0 0 1 1 4
total score: 6

Алгоритм O (n ^ 2) тривиален, но я подозреваю, что это возможно сделать в O (nlgn), отсортировав массив.У кого-нибудь есть идеи, как это сделать, или если это невозможно?

Answer 1

Похоже, что вы, по сути, подсчитываете количество пар элементов, которые находятся в неправильном относительном порядке (т.е. число инверсий ).Это можно сделать в O (n * log (n)), используя ту же идею, что и сортировка слиянием.При слиянии вы просто подсчитываете количество элементов, которые находятся в левом списке, но должны были быть в правом списке (и наоборот).

Answer 2

Если диапазон ваших чисел достаточно мал, самый быстрый алгоритм, который я могу придумать, это алгоритм, который использует Fenwick Trees .По сути, просто выполните итерацию по списку и запросите дерево Фенвика, сколько элементов перед ним, затем вставьте число в дерево.Это ответит на ваш вопрос в O (nlogm), где n - размер вашего списка, а m - ваше наибольшее целое число.

Если у вас нет разумного диапазона целых чисел (или вы хотите сохранитьпробел) Решение MAK чертовски элегантно, так что используйте его:)