首页 文章

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

提问于
浏览 次
0

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

enter image description here

可以在页面上找到进一步的说明 . 例如，将'swapped'队列表示为 q ，如果 q = [2, 1, 5, 3, 4] ，那么所需的交换次数为3：

enter image description here

根据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.但是，对于所有其他“隐藏”测试用例，它给出了错误的答案：

enter image description here

我也试过一个实现冒泡排序的提交：

#!/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)

但是相同（失败）的结果 . 互换的最小数量是否不等于反转次数或通过冒泡排序获得的数量？

python algorithm sorting

3 回答

  • 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)]

    你试图在你的RAM中存储 10^10 元组 .

    你的第二个代码的问题是你正在使用diff的元素的 abs 来确保数组不是混乱的 . 然而，一个人只能通过贿赂才能到达终点，并且不会出现两个以上的位置，而不是相反 .

    回复于
  • 0

    Swift 4版本：

    func minimumBribes(queue: [Int]) -> Int? {

  for (index, value) in queue.enumerated() {
     if value - (index + 1) > 2 { // `+ 1` needed because index starts from `0`, not from `1`.
        return nil
     }
  }
  var counter = 0
  var queue = queue // Just a mutable copy of input value.
  while true {
     var isSorted = true
     for i in 0 ..< queue.count - 1 {
        if queue[i] > queue[i + 1] {
           queue.swapAt(i, i + 1)
           counter += 1
           isSorted = false
        }
     }
     if isSorted {
        break
     }
  }
  return counter
}

// Complete the minimumBribes function below.
func minimumBribes(q: [Int]) -> Void {

    if let value = minimumBribes(queue: q) {
        print("\(value)")
    } else {
        print("Too chaotic")
    }

}
    回复于
  • 0

    干净的python解决方案：

    def minimumBribes(q):
    b = 0
    for i, x in enumerate(q):
        if x - i > 3:
            print('Too chaotic')
            return
        for y in q[max(0, x - 2):i]:
            if y > x:
                b += 1
    print(b)
    回复于

相关问题