计算列表中的对，使得它们的第一个索引小于第二个但第一个元素大于第二个

Question

我有列表 [5,2,10,9,7]。
我想统计所有满足条件( i<j and list[i]>list[j] )
的对例如，5 的索引小于 2 的索引，但 5 大于 2，因此将计数器增加 1，对于 (10,9) 和 (10,7) 以及 (9,7) 也是如此，因此值计数器的值为 4

我已经解决了这个问题，但是复杂度为O(n^2)，但是我想找到一个时间复杂度最低的解决方案。

这是在 O(n^2) 上运行的代码

 def ques(lista):
     b=0
     for i in range (len(lista)):
        for j in range (1,len(lista)):
            if i<j and lista[i]> lista[j] : 
                b+=1
     return b

Answer 1

Mergesort 应该能够在 O(nlogn) 中完成此操作。在合并过程中，当我们要合并左右数组时，我们比较两个数组的第一个元素，如果右数组的第一个元素小于当前左数组的第一个数组，则弹出它，添加它到一个新的临时数组。同时将计数器增加左数组的长度（因为左数组中的所有元素都更大但索引更小）。

def mergeSort(a):
    if len(a) >= 2:
        mid = len(a)//2
        left, right = mergeSort(a[:mid]), mergeSort(a[mid:])
        temp = []
        i, j = 0, 0
        for _ in range(len(a)):
            if i < len(left) and j < len(right):
                if  right[j] < left[i]:
                    temp.append(right[j])
                    # here we are counting are our pairs
                    counter[0] += len(left)-i
                    j += 1
                else:
                    temp.append(left[i])
                    i += 1
            elif i < len(left):
                temp.append(left[i])
                i += 1
            else:
                temp.append(right[j])
                j += 1
        return temp
    else:
        return a


counter = [0]
arr = [5, 2, 10, 9, 7]
mergeSort(arr)
print(counter[0])

Answer 2

我不认为它可以在小于 O(n^2) 的时间内完成：

每个元素都应该与它之后的所有元素进行比较，这意味着对于第一个元素，我们需要： n-1次比较，对于后面的元素我们需要n-2次比较等等。

(n-1) + (n-2) + (n-3) + ... + 2 + 1 => order of n^2

计算列表中的对，使得它们的第一个索引小于第二个但第一个元素大于第二个

Counting the pairs in a list such that their first index is less than the second but the first element is greater than the second

python

list

time-complexity