第 20 天：在 Hackerrank 中排序，Python

Question

最近我一直在做 HackerRank 30 天的代码挑战，并使用 Python 解决挑战。但是在第 20 天（关于冒泡排序算法）我无法解决它。这是 Hackerrank 中任务的 link，下面是我的代码。

import sys

n = int(raw_input().strip())
a = map(int, raw_input().strip().split(' '))
numSwap = 0

for first in a:
    b = a[a.index(first)+1:]
    for second in b:
        if first > second:
            a[a.index(first)] = second
            a[a.index(second)] = first
            numSwap += 1

firstElement = a[0]
lastElement = a[len(a)-1]
print "Array is sorted in %d swaps\nFirst Element: %s\nLast Element: %d " %(numSwap, firstElement, lastElement)

此代码的输入是：

3
3 2 1

代码的结果是：

Array is sorted in 3 swaps  
First Element: 3  
Last Element: 1

预期结果：

Array is sorted in 3 swaps.
First Element: 1
Last Element: 3

问题是为什么它没有像预期的那样工作？代码的哪一部分是错误的？谢谢。

Answer 1

您的代码存在问题以及它未按预期工作的原因是：

for first in a:
b = a[a.index(first)+1:]
for second in b:
    if first > second:
        a[a.index(first)] = second
        a[a.index(second)] = first
        numSwap += 1

您正在交换第一个数组 a 中的元素，但没有更新第二个数组 b 中的相同元素。

这里有一个应该可以完美运行的解决方案：

import sys

n = int(raw_input().strip())
a = map(int, raw_input().strip().split(' '))
# Write Your Code Here
numberOfSwaps = 0
for i in xrange(n):
    for j in xrange(n-1):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
            numberOfSwaps += 1
    if not numberOfSwaps:
        break


print "Array is sorted in", numberOfSwaps, "swaps."
print "First Element:", a[0]
print "Last Element:", a[n-1]

干杯:)

Answer 2

我终于知道我的代码有什么错误了。

for first in a:
    b = a[a.index(first)+1:]
    for second in b:
        if first > second:
            a[a.index(first)] = second
            a[a.index(second)] = first
            numSwap += 1

因此下面的这些代码将元素交换回其原始位置：

a[a.index(first)] = second
a[a.index(second)] = first

应该创建一个变量来包含其中一个元素。

smaller = a.index(first)
bigger = a.index(second)
a[smaller] = second
a[bigger] = big

我的第二个错误是第一个 for 不会重复新更新列表中的算法，导致 2 作为第一个元素。

正确的代码是 TheDarkKnight 写的。

Here's a solution that should work flawlessly:

import sys

n = int(raw_input().strip())
a = map(int, raw_input().strip().split(' '))
# Write Your Code Here
numberOfSwaps = 0
for i in xrange(n):
    for j in xrange(n-1):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
            numberOfSwaps += 1
    if not numberOfSwaps:
        break


print "Array is sorted in", numberOfSwaps, "swaps."
print "First Element:", a[0]
print "Last Element:", a[n-1]

Cheers :)

第 20 天：在 Hackerrank 中排序，Python

Day 20: Sorting in Hackerrank, Python

python

bubble-sort

python-2.7