时间戳

首页 > 解决方案 > 为什么这个解决方案没有陷入无限循环？

python - 为什么这个解决方案没有陷入无限循环？

问题描述

我解决了 HackerRank ( https://www.hackerrank.com/challenges/minimum-swaps-2/problem ) 上的 Minimum Swaps 2 数组挑战。我的解决方案会因更大的数组而超时，所以我回去重构代码。我想到了我的新解决方案，我几乎一提交就意识到它行不通。然而，它确实......完美，但我要疯了试图找出原因。最起码，为什么它不会陷入一个无休止的 while 循环反复来回交换两个数组值？撇开显而易见的不谈，假设它确实神奇地跳出了循环，如果我们正在寻找最小值，它怎么可能在它用来计算交换的条件下得到正确的答案互换次数？我在代码的不同点添加了打印语句，以尝试查看发生了什么并自己理解它，但它们只会增加混乱。有人能告诉我我荒谬的天才的逻辑吗？还是这是侥幸？

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the minimumSwaps function below.
def minimumSwaps(arr):
    swaps = 0

    for x in range(0, n - 1):
        while arr[x] != x + 1:
            arr[arr[x] - 1], arr[x] = arr[x], arr[arr[x] - 1]
            swaps += 1

    return swaps


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    arr = list(map(int, input().rstrip().split()))

    res = minimumSwaps(arr)

    fptr.write(str(res) + '\n')

    fptr.close()

标签： pythonarrays

解决方案

只是如果你想按照你的步骤

                             list  swap_index_1  swap_index_2
0  [7, 9, 6, 4, 2, 5, 1, 3, 8, 0]           NaN           NaN
1  [1, 9, 6, 4, 2, 5, 7, 3, 8, 0]           0.0           0.0
2  [1, 8, 6, 4, 2, 5, 7, 3, 9, 0]           1.0           7.0
3  [1, 3, 6, 4, 2, 5, 7, 8, 9, 0]           1.0           2.0
4  [1, 6, 3, 4, 2, 5, 7, 8, 9, 0]           1.0           5.0
5  [1, 5, 3, 4, 2, 6, 7, 8, 9, 0]           1.0           4.0
6  [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]           1.0           1.0

from random import shuffle
import pandas as pd
steps = []


def log(arr, s1, s2):
    steps.append(dict(list=arr.copy(), swap_index_1=s1, swap_index_2=s2))


n = 10
arr = list(range(n))
shuffle(arr)

swaps = 0

log(arr, None, None)

for x in range(0, n - 1):
        while arr[x] != x + 1:
            arr[arr[x] - 1], arr[x] = arr[x], arr[arr[x] - 1]
            swaps += 1

            log(arr, x, arr[x] - 1)

steps = pd.DataFrame(steps)
print(steps)

推荐阅读