Привет, кодеры, сегодня мы увидим проблему, основанную на алгоритме сортировки слиянием.
Итак, в задаче нам дан массив A размера n, и мы должны подсчитать количество инверсий в этом массиве.
Определение счетчика инверсии, данное в условии задачи, выглядит следующим образом.
Счетчик инверсии.Для массива счетчик инверсии показывает, насколько далек (или близок) массив от сортировки. Если массив уже отсортирован, то счетчик инверсии равен 0. Если массив отсортирован в обратном порядке, то счетчик инверсии будет максимальным.
Формально два элемента a[i] и a[j] образуют инверсию, если a[i] › a[j] и i ‹ j.
Подход грубой силы:
Поскольку приведенное выше решение приведет к ошибке времени выполнения Time Limit Exceed Exceed, мы должны оптимизировать его.
Оптимальный подход:
Здесь мы используем концепцию сортировки слиянием,
поэтому сначала мы делим массив на две половины, пока не получим каждый из одного элемента (первый шаг классического алгоритма сортировки слиянием)
затем мы начинаем объединять его, сохраняя во внимание определение Inversion Count.
т. е. каждый раз, когда мы объединяем 2 части массива, мы рассматриваем a[i]›a[j]
а также мы можем наблюдать тот факт, что каждый раз, когда мы делаем сравнение, мы имеем два отсортированных массива левый массив и правый массив,поэтому для конкретного элемента левого левого массива, если условие a[i]›a[j] верно, то мы можем посчитать все элементы, расположенные справа от левого массива.
Код:
Временная сложность: O(n log(n))
Пространственная сложность: O(n)
Спасибо ! за прочтение этой статьи 😀😉
Теперь вы также можете попробовать эту задачу для практики.
https://leetcode.com/problems/reverse-pairs/
Использованная литература:
