Нахождение количества инверсий

Question

Нужно найти количество инверсий, если Число1 больше числа2 и индекс числа1 меньше индекса числа2 то это будет являться инверсией

n = int(input())
list1 = list()
res = 0
for range1 in range(n):
    k=int(input())
    list1.append(k)
for range2 in range(len(list1)):
    for range3 in range(range2+1,len(list1)): 
        if list1[range2] > list1[range3] and range2 < range3:
            res+=1
print(res)

Answer 1

Вариант 1:

A = list(int(input()) for _ in range(int(input())))
c = 0
for i in range(len(A)):
    for j in range(i+1, len(A)):
        if A[i] > A[j]:
            c += 1
print(c)

Вариант 2:

A = list(int(input()) for _ in range(int(input())))
print(sum(A[i]>A[j] for i in range(len(A)) for j in range(i+1, len(A))))

Вариант 3:

A = list(int(input()) for _ in range(int(input())))
print(len([1 for i in range(len(A)) for j in range(i+1, len(A)) if A[i]>A[j]]))

Answer 2

Я бы сделал так:

arr = []
res = 0
for _ in range(int(input())):
    n = int(input())
    res += sum(el > n for el in arr)
    arr.append(n)

print(res)

Answer 3

Количество элементов 10^5 обычно подразумевает, что решение за квадрат не пройдёт, а вот O(nlogn) - устроит.

Для достижения такой сложности можно использовать сортировку слиянием. В процедуре слияния (merge) есть такой шаг, когда в результат пишется элемент из правой половины. Вот в этот момент нужно к (локальному) счётчику инверсий добавить количество ещё неиспользованных элементов левой половины.

invcount = 0
...
if left[i] <= right[j]:
      a[k] = left[i]
      i += 1
      k += 1    
else:
      a[k] = right[j]
      invcount += length(left) - i
      j += 1
      k += 1    
...
return invcount

А в рекурсивной процедуре mergesort нужно сложить количество инверсий в левой половине, количество в правой, и количество инверсий, возникающих при слиянии (то, что возвращает merge)

... разделение массива на две части
return mergesort(left) + mergesort(right) + merge(left, right)

БЛОГ НА HUSL

Нахождение количества инверсий

Ответы (3 шт):