如何将嵌套循环转换为列表理解？

Question

我正在尝试解决一道算法题。

给定一个数组，计算它的反转次数。比 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

我的解决方案基于此 link

我知道我的语法不正确，尤其是 inv_count += 1 我已经寻找了嵌套循环需要 return 计数的示例，并且是使用列表理解编写的，但我不能'找不到。

理想情况下，函数应该像这样告诉数组中的反转次数；

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

Answer 1

sum([1 if (arr[i] > arr[j]) else 0 for i in range(n) for j in range(i+1,n)])

应该作为列表理解答案。几个月前我曾提到 this Whosebug post 做能够做到这一点。

但是，就时间复杂度而言，它不会比 O(N^2) 好。

如何将嵌套循环转换为列表理解？

How to convert nested loop to list comprehension?

arrays

big-o

list-comprehension

nested-loops

python-3.x

给定一个数组，计算它的反转次数。比 O(N^2) 时间更快。

输出

输出