Count Inversions

Q: Qu’est-ce qu’une inversion dans un tableau ?

Une inversion est une paire de positions i < j où nums[i] > nums[j] : une valeur plus grande se trouve donc avant une valeur plus petite. Une liste triée comporte 0 inversion, et une liste inversée de valeurs distinctes en comporte le plus, soit n(n-1)/2 . Ce nombre correspond au nombre d’échanges entre voisins effectués par le tri à bulles.

Q: Quelle est la complexité temporelle du comptage des inversions avec le tri fusion ?

Temps en O(n log n) et espace supplémentaire en O(n) pour le tampon de fusion. Chacun des log n niveaux de fusion parcourt chaque valeur une fois, soit environ 3 × 10^5 étapes pour 2 × 10^4 valeurs. La boucle qui traite les paires une par une est en O(n²) .

MoyenTri Récursivité

+10

Étant donné une liste d’entiers nums, renvoie le nombre d’inversions : les paires d’indices i < j telles que nums[i] > nums[j], c’est-à-dire une valeur plus grande avant une valeur plus petite. Des valeurs égales ne forment jamais une inversion, et une liste triée n’en contient aucune.

Fonction

countInversions(nums: integer-array) → integer

numsinteger-array: la liste d’entiers
Renvoieinteger: le nombre de paires i < j telles que nums[i] > nums[j]

Contraintes

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
La réponse est au plus n(n-1)/2 < 2 × 10⁸, elle tient donc dans un entier signé de 32 bits.

Exemples

Entrée: nums = [5, 3, 8, 1, 4]
Sortie: 6
Explication: 5 vient avant 3, 1 et 4 : 3 paires. 3 vient avant 1, et 8 avant 1 et 4 : 3 de plus. 1 et 4 sont dans le bon ordre, donc le total est de 6.

Pour aller plus loin

Qu'est-ce qui change si une paire ne compte que lorsque nums[i] > 2 × nums[j] ? Le tri fusion peut-il toujours compter ces paires en O(n log n) ?

Solution

Vérifier chaque paire nécessite environ n² / 2 comparaisons. Le tri fusion compte les paires en bloc : lorsqu’une valeur de la moitié droite est placée pendant une fusion, toutes les valeurs de gauche encore en attente sont plus grandes et la précèdent. Une soustraction compte tout ce groupe, donc le comptage ne coûte rien de plus que le tri en O(n log n).

Vérifiez chaque paire

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Pour chaque indice i, vérifiez chaque indice ultérieur j et ajoutez 1 lorsque nums[i] > nums[j]. C’est la définition, et la comparaison stricte exclut les valeurs égales.

Le coût est de n(n-1)/2 comparaisons : presque 2 × 10^8 pour 2 × 10^4 valeurs, et doubler n le multiplie par quatre.

Algorithme

Définissez count = 0.
Pour chaque i de 0 à n-1, et chaque j de i + 1 à n-1, ajoutez 1 à count lorsque nums[i] > nums[j].
Retournez 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

Tri par fusion avec comptage pendant la fusion

Intuition

Divise la liste au milieu. Une inversion contient ses deux valeurs dans la moitié gauche, ses deux valeurs dans la moitié droite, ou une valeur de chaque côté. L’appel récursif sur chaque moitié compte les inversions des deux premiers types et trie cette moitié. Le tri déplace les valeurs uniquement au sein d’une moitié, donc chaque valeur de gauche reste avant chaque valeur de droite, et les paires qui se croisent restent inchangées.

Lors de la fusion, si left[i] ≤ right[j], place left[i] : toutes les valeurs de droite encore en attente sont au moins égales à right[j], elles ne forment donc aucune inversion. Sinon, right[j] est inférieur à left[i] et, puisque la moitié gauche est triée, à toutes les valeurs de gauche encore en attente. Ajoute leur nombre. En plaçant la valeur de gauche en cas d’égalité, on exclut les valeurs égales.

Dans [5, 3, 8, 1, 4], les moitiés contiennent 1 et 2 inversions. En fusionnant [3, 5] et [1, 4, 8], 1 passe devant 3 et 5, et 4 passe devant 5 : 1 + 2 + 3 = 6.

Algorithme

Copiez nums et créez un tampon de même longueur.
Pour trier et compter une plage contenant moins de 2 valeurs, renvoyez 0.
Sinon, divisez-la à mid, puis triez et comptez chaque moitié.
Fusionnez les moitiés à l’aide du tampon : si left[i] ≤ right[j], prenez la valeur de gauche ; sinon, prenez la valeur de droite et ajoutez le nombre de valeurs de gauche qui n’ont pas encore été placées.
Recopiez la plage fusionnée et renvoyez la somme des trois comptes.

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

Pièges et cas limites

Ajouter 1 lorsqu’une valeur de droite est placée. Elle dépasse toutes les valeurs de gauche encore en attente, donc ajoute leur nombre, mid - i.
Prendre la valeur de droite en cas d’égalité, en utilisant left[i] < right[j] comme test pour le côté gauche. Alors, [2, 2, 2, 1] compte les 2 égaux entre eux et renvoie plus de 3. Utilise ≤.
Compter pendant la copie des éléments restants après l’épuisement d’une moitié. Les valeurs de gauche restantes n’ont aucune valeur de droite après elles, et les valeurs de droite restantes ont déjà été comparées à toutes les valeurs de gauche.

Questions fréquentes3

Qu’est-ce qu’une inversion dans un tableau ?

Une inversion est une paire de positions i < j où nums[i] > nums[j] : une valeur plus grande se trouve donc avant une valeur plus petite. Une liste triée comporte 0 inversion, et une liste inversée de valeurs distinctes en comporte le plus, soit n(n-1)/2. Ce nombre correspond au nombre d’échanges entre voisins effectués par le tri à bulles.

Quelle est la complexité temporelle du comptage des inversions avec le tri fusion ?

Temps en O(n log n) et espace supplémentaire en O(n) pour le tampon de fusion. Chacun des log n niveaux de fusion parcourt chaque valeur une fois, soit environ 3 × 10^5 étapes pour 2 × 10^4 valeurs. La boucle qui traite les paires une par une est en O(n²).

Peut-on compter les inversions sans tri fusion ?

Oui. Un arbre de Fenwick (arbre indexé binaire) sur les rangs des valeurs parcourt la liste une fois et, pour chaque valeur, demande combien de valeurs précédentes sont plus grandes, en O(log n) par valeur. Cela donne également O(n log n) au total. Un arbre de recherche équilibré qui suit la taille des sous-arbres fonctionne de la même manière.

def countInversions(nums):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

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

Résultat attendu