python - 对数组进行冒泡排序所需的最小交换次数是多少？

Question

我正在尝试解决 Hackerrank 问题 New Year Chaos :

可以在页面上找到进一步的解释。例如，将“交换”队列表示为 q，如果 q = [2, 1, 5, 3, 4]，则所需的交换次数为 3:

根据https://www.quora.com/How-can-I-efficiently-compute-the-number-of-swaps-required-by-slow-sorting-methods-like-insertion-sort-and-bubble-sort-to-sort-a-given-array的第一个回答，冒泡排序所需的交换次数等于数组中的反转次数。我尝试使用以下 Hackerrank 提交来对此进行测试:

#!/bin/python

import sys


T = int(raw_input().strip())
for a0 in xrange(T):
    n = int(raw_input().strip())
    q = map(int,raw_input().strip().split(' '))
    # your code goes here
    diff = [x - y for x, y in zip(q, range(1,n+1))]
    if any([abs(el) > 2 for el in diff]):
        print "Too chaotic"
    else:
        all_pairs = [(q[i], q[j]) for i in range(n) for j in range(i+1, n)]
        inversions = [pair[0] > pair[1] for pair in all_pairs]
        print inversions.count(True)

这里还有一个在本地运行的代码版本:

n = 5
q = [2, 1, 5, 3, 4]

diff = [x - y for x, y in zip(q, range(1,n+1))]
if any([abs(el) > 2 for el in diff]):
    print "Too chaotic"
else:
    all_pairs = [(q[i], q[j]) for i in range(n) for j in range(i+1, n)]
    inversion_or_not = [pair[0] > pair[1] for pair in all_pairs]
    print inversion_or_not.count(True)

对于给定的测试用例，脚本正确地打印了数字 3。但是，对于所有其他“隐藏”的测试用例，它给出了错误的答案:

我还尝试了一个实现冒泡排序的提交:

#!/bin/python

import sys

def swaps_bubble_sort(q):
    q = list(q)         # Make a shallow copy
    swaps = 0
    swapped = True
    while swapped:
        swapped = False
        for i in range(n-1):
            if q[i] > q[i+1]:
                q[i], q[i+1] = q[i+1], q[i]
                swaps += 1
                swapped = True
    return swaps

T = int(raw_input().strip())
for a0 in xrange(T):
    n = int(raw_input().strip())
    q = map(int,raw_input().strip().split(' '))
    # your code goes here
    diff = [x - y for x, y in zip(q, range(1,n+1))]
    if any([abs(el) > 2 for el in diff]):
        print "Too chaotic"
    else:
        print swaps_bubble_sort(q)

但结果相同(失败)。最小交换次数是否不等于反转次数或冒泡排序获得的次数？

Answer 1

您只需计算冒泡排序中必要的交换次数。这是我的代码已被接受。

T = input()
for test in range(T):
    n = input()
    l = map(int, raw_input().split())
    for i,x in enumerate(l):
        if x-(i+1) > 2:
            print "Too chaotic"
            break
    else:
        counter = 0
        while 1:
            flag = True
            for i in range(len(l)-1):
                if l[i] > l[i+1]:
                    l[i],l[i+1] = l[i+1],l[i]
                    counter += 1
                    flag = False
            if flag:
                break
        print counter

在您的第一个代码中，您的方法是 O(n^2)，这不适用于 n = 10^5。在这一行中

all_pairs = [(q[i], q[j]) for i in range(n) for j in range(i+1, n)]

您正在尝试将 10^10 元组存储在您的 RAM 中。

第二个代码的问题是您使用 diff 元素的 abs 来确保数组不困惑。但是一个人只有通过贿赂才能走到最后，这并不违反规定。因此，您只需确保一个人不会出现超过两个职位，而不是相反。