计数反转算法中的错误

Question

我正在尝试编写一种算法来计算数组中的反转次数。反转是 A[i] > A[j] 和 i < j。

def sort_and_count(L):

    if len(L)<2:

        return 0, L

    else:

        A = L[:len(L)//2]

        B = L[len(L)//2:]

        rA, A = sort_and_count(A)

        rB, B = sort_and_count(B)

        r, L = merge_and_count(A,B)

    return r+rB+rA, L

def merge_and_count(A,B):

    i = j = 0

    count = 0

    L = []

    while len(A) > i and len(B) > j:

        if A[i] <= B[j]:

            L.append(A[i])

            i+=1

        else:

            L.append(B[j])

            count = count + (len(A)-1)

            j+=1

    #copy the remaining elements

    for index in range(i,len(A)):

        L.append(A[index])

    for index in range(j,len(B)):

        L.append(B[index])

    return count, L

sort_and_count(A)[0]

算法不正确。对于这个输入 A = [7, 3, 20, 16, 5, 8] 它返回 6。正确答案是 7 (7, 3),(7, 5),(20, 16),(20, 5) ,(20, 8),(16, 5),(16, 8)。对于某些输入，答案是正确的。我不确定是什么原因造成的。

Answer 1

我希望我知道它给出正确结果的输入是什么。你有一个错字：len(A) - 1应该是len(A) - i。