Я пытаюсь решить вопрос алгоритма.
Учитывая массив, подсчитайте количество инверсий, которые у него есть. Сделайте это быстрее, чем за O (N ^ 2) раз.
мое первое решение, которое не удовлетворяет O (N ^ 2), использует вложенные циклы:
def getInvCount(arr, n):
inv_count = 0
for i in range(n):
for j in range(i + 1, n):
if (arr[i] > arr[j]):
inv_count += 1
return inv_count
Моя попытка перейти к пониманию списка
def getInvCount(arr, n):
inv_count = 0
inv_count = [j for i in range (n) for j in range(i + 1, n) if (arr[i] > arr[j])]
inv_count += 1
return inv_count
Я основываю свое решение на этой ссылке
Я понимаю, что не правильно понимаю свой синтаксис, особенно inv_count += 1 Я искал примеры, когда вложенный цикл должен возвращать счет и записан с использованием списка, но я не смог его найти.
В идеале функция должна сообщать количество инверсий в массиве, например так:
def getInvCount(arr, n):
inv_count = 0
for i in range(n):
for j in range(i + 1, n):
if (arr[i] > arr[j]):
inv_count += 1
return inv_count
#testdata
arr = [1, 20, 6, 4, 5]
n = len(arr)
print("Number of inversions are", getInvCount(arr, n))
выход
Number of inversions are 5
с моим текущим решением
def getInvCount(arr, n):
inv_count = 0
inv_count = [j for i in range (n) for j in range(i + 1, n) if (arr[i] > arr[j])]
inv_count += 1
return inv_count
#testdata
arr = [1, 20, 6, 4, 5]
n = len(arr)
print("Number of inversions are", getInvCount(arr, n))
выход
Traceback (most recent call last):
File "and.py", line 24, in <module>
getInvCount(arr, n))
File "and.py", line 16, in getInvCount
inv_count += 1
TypeError: 'int' object is not iterable