Count Inversions

Q: O que é uma inversão em um array?

Uma inversão é um par de posições i < j em que nums[i] > nums[j] , ou seja, um valor maior vem antes de um menor. Uma lista ordenada tem 0 inversões, e uma lista invertida de valores distintos tem o número máximo, n(n-1)/2 . A contagem equivale ao número de trocas entre vizinhos que o bubble sort realiza.

Q: Qual é a complexidade de tempo da contagem de inversões com merge sort?

Tempo O(n log n) e espaço extra O(n) para o buffer de intercalação. Cada um dos log n níveis de intercalação percorre cada valor uma vez, cerca de 3 × 10^5 etapas para 2 × 10^4 valores. O loop par a par é O(n²) .

MédioOrdenação Recursão

+10

Dada uma lista de números inteiros nums, retorne o número de inversões: pares de índices i < j com nums[i] > nums[j], em que um valor maior aparece antes de um menor. Valores iguais nunca formam uma inversão, e uma lista ordenada não tem nenhuma.

Função

countInversions(nums: integer-array) → integer

numsinteger-array: a lista de números inteiros
Retornainteger: o número de pares i < j em que nums[i] > nums[j]

Restrições

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
A resposta é no máximo n(n-1)/2 < 2 × 10⁸, então cabe em um inteiro com sinal de 32 bits.

Exemplos

Entrada: nums = [5, 3, 8, 1, 4]
Saída: 6
Explicação: 5 vem antes de 3, 1 e 4: 3 pares. 3 vem antes de 1, e 8 vem antes de 1 e 4: mais 3. 1 e 4 estão em ordem, então o total é 6.

Para ir além

O que muda se um par só contar quando nums[i] > 2 × nums[j]? A ordenação por intercalação ainda consegue contar esses pares em O(n log n)?

Solução

Verificar cada par leva cerca de n² / 2 comparações. O merge sort conta pares em lote: quando um valor da metade direita é colocado durante uma intercalação, todos os valores da esquerda que ainda estão esperando são maiores e vieram antes dele. Uma subtração conta todo esse grupo, então a contagem não custa nada além da ordenação O(n log n).

Verifique cada par

Correta, mas não termina nos maiores testes

Intuição

Para cada índice i, verifique cada índice posterior j e some 1 quando nums[i] > nums[j]. Essa é a definição, e a comparação estrita exclui valores iguais.

O custo é de n(n-1)/2 comparações: quase 2 × 10^8 para 2 × 10^4 valores, e dobrar n faz esse custo quadruplicar.

Algoritmo

Defina count = 0.
Para cada i de 0 a n-1 e cada j de i + 1 a n-1, adicione 1 a count quando nums[i] > nums[j].
Retorne 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

Ordenação por intercalação que conta durante a intercalação

Intuição

Divida a lista ao meio. Uma inversão tem os dois valores na metade esquerda, os dois na metade direita ou um em cada lado. Recursar em cada metade conta os dois primeiros tipos e ordena essa metade. A ordenação move valores apenas dentro de uma metade, então todo valor da esquerda continua vindo antes de todo valor da direita, e os pares que cruzam as metades permanecem inalterados.

Na intercalação, se left[i] ≤ right[j], coloque left[i]: todo valor da direita que ainda está esperando é pelo menos tão grande quanto right[j], então ele não forma uma inversão. Caso contrário, right[j] é menor que left[i] e, como a metade esquerda está ordenada, menor que todos os valores da esquerda que ainda estão esperando. Some a quantidade deles. Colocar o valor da esquerda em caso de empate mantém os valores iguais fora da contagem.

Em [5, 3, 8, 1, 4], as metades contêm 1 e 2 inversões. Ao intercalar [3, 5] com [1, 4, 8], 1 passa por 3 e 5, e 4 passa por 5: 1 + 2 + 3 = 6.

Algoritmo

Copie nums e crie um buffer do mesmo tamanho.
Para ordenar e contar um intervalo com menos de 2 valores, retorne 0.
Caso contrário, divida-o em mid e ordene e conte cada metade.
Mescle as metades usando o buffer: se left[i] ≤ right[j], escolha o valor da esquerda; caso contrário, escolha o valor da direita e some o número de valores da esquerda que ainda não foram posicionados.
Copie o intervalo mesclado de volta e retorne a soma das três contagens.

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))

Armadilhas e casos extremos

Adicionar 1 quando um valor da direita é colocado. Ele ultrapassa todos os valores da esquerda que ainda estão aguardando, então adicione a quantidade deles: mid - i.
Escolher o valor da direita em caso de empate, usando left[i] < right[j] como teste para o lado esquerdo. Então, [2, 2, 2, 1] conta os 2s iguais uns contra os outros e retorna mais de 3. Use ≤.
Contar ao copiar os valores restantes depois que uma das metades se esgota. Os valores restantes da esquerda não têm nenhum valor da direita depois deles, e os valores restantes da direita já foram comparados com todos os valores da esquerda.

Perguntas frequentes3

O que é uma inversão em um array?

Uma inversão é um par de posições i < j em que nums[i] > nums[j], ou seja, um valor maior vem antes de um menor. Uma lista ordenada tem 0 inversões, e uma lista invertida de valores distintos tem o número máximo, n(n-1)/2. A contagem equivale ao número de trocas entre vizinhos que o bubble sort realiza.

Qual é a complexidade de tempo da contagem de inversões com merge sort?

Tempo O(n log n) e espaço extra O(n) para o buffer de intercalação. Cada um dos log n níveis de intercalação percorre cada valor uma vez, cerca de 3 × 10^5 etapas para 2 × 10^4 valores. O loop par a par é O(n²).

É possível contar inversões sem usar merge sort?

Sim. Uma árvore de Fenwick (árvore indexada binária) sobre as posições dos valores percorre a lista uma vez e, para cada valor, pergunta quantos valores anteriores são maiores, em O(log n) por valor. Isso também resulta em O(n log n) no total. Uma árvore de busca balanceada que rastreia os tamanhos das subárvores funciona da mesma forma.

def countInversions(nums):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada