python - 计数反转算法的不稳定行为(python)

Question

首先，反转是无序列表中的数字对，其中两个数字中较大的数字位于较小数字的左侧。在以下列表中:[ 1, 3, 5, 2, 4, 6 ] 有 3 个反转:(3,2)、(5,2) 和 (5,4)

这是我计算倒置的代码:

def num_inv(array):
    count = count_left = count_right = 0
    if len(array)<=1:
        return 0

    mid = len(array)//2
    left_array = array[:mid]
    right_array = array[mid:]

    count_left = num_inv(array[:mid])
    count_right = num_inv(array[mid:])


    i = j =  k = 0

    while i < len(left_array) and j < len(right_array):
        if left_array[i] <= right_array[j]:
            array[k] = left_array[i]
            i+=1
        else:
            array[k] = right_array[i]
            j +=1
            count += len(left_array[i:])
        k+=1   


    while i <len(left_array):
        array[k] = left_array[i]
        i+=1
        k+=1


    while j <len(right_array):
        array[k] = right_array[j]
        j+=1
        k+=1


    return count + count_left + count_right

在我的测试用例(大部分)中它给出了正确的结果，但有时它是错误的。你能看看并告诉我代码有什么问题吗？我在调试上花费了大量时间，因此我需要重新审视我的代码。

测试用例:t4 输出不正确的结果

t1 = [1,3,5,2,4,6]
print("Testing using", t1)
print("Expecting:", 3)
print("Returned:", num_inv(t1))

t2 = [1,5,3,2,4]
print("\nTesting using", t2)
print("Expecting:", 4)
print("Returned:", num_inv(t2))

t3 = [5,4,3,2,1]
print("\nTesting using", t3)
print("Expecting:", 10)
print("Returned:", num_inv(t3))

t4 = [1,6,3,2,4,5]
print("\nTesting using", t4)
print("Expecting:", 5)
print("Returned:", num_inv(t4))

t5 = [1,2,3,4,5,6]
print("\nTesting using", t5)
print("Expecting:", 0)
print("Returned:", num_inv(t5))

Answer 1

首先，您比较 left_array[i] <= right_array[j]在你的第一个while循环，然后你从 right_array[i] 复制.这一定是个错误，但这并不是算数的原因。

在更正之后，我在您的代码中添加了一行，即诊断 print()第一个 while 循环中的语句:

while i < len(left_array) and j < len(right_array):
    if left_array[i] <= right_array[j]:
        array[k] = left_array[i]
        i+=1
    else:
        array[k] = right_array[j]
        j +=1
        print("Counting as inversions of", array[k], ":", left_array[i:])
        count += len(left_array[i:])
    k+=1   

然后我运行了你的测试t4 ，得到如下输出:

Testing using [1, 6, 3, 2, 4, 5]
Expecting: 5
Counting as inversions of 3 : [6]
Counting as inversions of 2 : [6, 3]
Counting as inversions of 4 : [6, 3]
Counting as inversions of 5 : [6, 3]
Returned: 7

明白了吗？当您找到一个倒置对时，假设(如您的代码所做的那样)left_array 的其余部分是不正确的。由反转(即大于 array[k] 的数字)组成。在这里，4 和 5 相对于 3 没有倒数。您必须以不同的方式计数。