Count Inversions

Q: Что такое инверсия в массиве?

Инверсия — это пара позиций i < j , для которых nums[i] > nums[j] , то есть большее значение стоит перед меньшим. В отсортированном списке 0 инверсий, а в списке из различных значений, упорядоченном в обратном порядке, их больше всего — n(n-1)/2 . Количество инверсий равно числу соседних перестановок, которые выполняет пузырьковая сортировка.

Q: Какова временная сложность подсчёта инверсий с помощью сортировки слиянием?

Время O(n log n) и дополнительная память O(n) для буфера слияния. На каждом из log n уровней слияния каждое значение обрабатывается один раз — около 3 × 10^5 шагов для 2 × 10^4 значений. Цикл с попарной обработкой имеет сложность O(n²) .

СреднеСортировка Рекурсия

+10

Для заданного списка целых чисел nums верните количество инверсий: пар индексов i < j, для которых nums[i] > nums[j], то есть больший элемент стоит перед меньшим. Равные значения никогда не образуют инверсию, а в отсортированном списке инверсий нет.

Функция

countInversions(nums: integer-array) → integer

numsinteger-array: список целых чисел
Возвращаетinteger: число пар i < j, для которых nums[i] > nums[j]

Ограничения

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Ответ не превышает n(n-1)/2 < 2 × 10⁸, поэтому он помещается в 32-разрядное целое число со знаком.

Примеры

Ввод: nums = [5, 3, 8, 1, 4]
Вывод: 6
Пояснение: 5 стоит перед 3, 1 и 4: 3 пары. 3 стоит перед 1, а 8 — перед 1 и 4: ещё 3. 1 и 4 расположены в правильном порядке, поэтому всего получается 6.

Дополнительный вопрос

Что изменится, если пара учитывается только тогда, когда nums[i] > 2 × nums[j]? Может ли сортировка слиянием по-прежнему подсчитывать такие пары за O(n log n)?

Решение

Проверка каждой пары требует около n² / 2 сравнений. Сортировка слиянием подсчитывает пары сразу группами: когда во время слияния помещается значение из правой половины, все значения из левой половины, которые ещё ожидают, больше него и стояли перед ним. Одно вычитание подсчитывает всю эту группу, поэтому подсчёт не требует ничего сверх сортировки за O(n log n).

Проверь каждую пару

Верно, но не успевает на самых больших тестах

Идея

Для каждого индекса i проверь каждый последующий индекс j и прибавь 1, если nums[i] > nums[j]. Это и есть определение, а строгое сравнение не учитывает равные значения.

Количество сравнений составляет n(n-1)/2: почти 2 × 10^8 для 2 × 10^4 значений, а удвоение n увеличивает его в четыре раза.

Алгоритм

Установи count = 0.
Для каждого i от 0 до n-1 и каждого j от i + 1 до n-1 увеличивай count на 1, когда nums[i] > nums[j].
Верни count.

def countInversions(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] > nums[j]:
                count += 1
    return count

Сортировка слиянием с подсчётом во время слияния

Идея

Разделите список пополам. Инверсия содержит оба значения из левой половины, оба из правой половины или по одному с каждой стороны. Рекурсивная обработка каждой половины подсчитывает инверсии первых двух видов и сортирует эту половину. Сортировка перемещает значения только внутри половины, поэтому каждое значение слева по-прежнему стоит перед каждым значением справа, а пересекающиеся пары не меняются.

При слиянии, если left[i] ≤ right[j], поместите left[i]: все ожидающие значения справа не меньше right[j], поэтому они не образуют инверсий. Иначе right[j] меньше left[i] и, поскольку левая половина отсортирована, меньше каждого ожидающего значения слева. Прибавьте их количество. Если значения равны, размещение значения слева первым не позволяет им образовать инверсию.

Для [5, 3, 8, 1, 4] в половинах содержится 1 и 2 инверсии. При слиянии [3, 5] и [1, 4, 8] значение 1 проходит перед 3 и 5, а 4 проходит перед 5: 1 + 2 + 3 = 6.

Алгоритм

Скопируй nums и создай буфер той же длины.
Если в диапазоне для сортировки и подсчёта меньше 2 значений, верни 0.
В противном случае раздели его в точке mid и отсортируй и подсчитай значения в каждой половине.
Объедини половины с помощью буфера: если left[i] ≤ right[j], возьми значение слева; иначе возьми значение справа и добавь количество ещё не размещённых значений слева.
Скопируй объединённый диапазон обратно и верни сумму трёх подсчётов.

def sortAndCount(a, buf, lo, hi):
    # Sorts a[lo:hi] and returns the number of inversions inside it.
    if hi - lo < 2:
        return 0
    mid = (lo + hi) // 2
    count = sortAndCount(a, buf, lo, mid) + sortAndCount(a, buf, mid, hi)
    # Merge the two sorted halves, counting the pairs that cross the middle.
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        if a[i] <= a[j]:
            buf[k] = a[i]
            i += 1
        else:
            # a[j] is smaller than every left value not placed yet: a[i..mid-1].
            buf[k] = a[j]
            j += 1
            count += mid - i
        k += 1
    while i < mid:
        buf[k] = a[i]
        i += 1
        k += 1
    while j < hi:
        buf[k] = a[j]
        j += 1
        k += 1
    a[lo:hi] = buf[lo:hi]
    return count


def countInversions(nums):
    a = list(nums)  # sort a copy, not the caller's list
    return sortAndCount(a, [0] * len(a), 0, len(a))

Ловушки и крайние случаи

Добавление 1, когда помещается правое значение. Оно обходит все ещё ожидающие левые значения, поэтому добавьте их количество: mid - i.
Выбор правого значения при равенстве, когда left[i] < right[j] используется как условие для выбора левой стороны. Тогда [2, 2, 2, 1] учитывает равные 2 при сравнении друг с другом и возвращает значение больше 3. Используйте ≤.
Подсчёт во время копирования оставшихся значений после того, как одна из половин закончилась. После оставшихся левых значений нет правых, а оставшиеся правые значения уже сравнивались со всеми левыми.

Частые вопросы3

Что такое инверсия в массиве?

Инверсия — это пара позиций i < j, для которых nums[i] > nums[j], то есть большее значение стоит перед меньшим. В отсортированном списке 0 инверсий, а в списке из различных значений, упорядоченном в обратном порядке, их больше всего — n(n-1)/2. Количество инверсий равно числу соседних перестановок, которые выполняет пузырьковая сортировка.

Какова временная сложность подсчёта инверсий с помощью сортировки слиянием?

Время O(n log n) и дополнительная память O(n) для буфера слияния. На каждом из log n уровней слияния каждое значение обрабатывается один раз — около 3 × 10^5 шагов для 2 × 10^4 значений. Цикл с попарной обработкой имеет сложность O(n²).

Можно ли подсчитать инверсии без сортировки слиянием?

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

def countInversions(nums):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

nums = [5, 3, 8, 1, 4]

Ожидаемый вывод