HackerRank(https://www.hackerrank.com/challenges/minimum-swaps-2/problem)でMinimum Swaps2アレイの課題を解決しました。私のソリューションはより大きな配列でタイムアウトするので、コードのリファクタリングに戻りました。私は新しい解決策に出くわしましたが、提出するとすぐに機能しないことに気づきました。しかし、それは完璧でした。しかし、私はその理由を理解しようとして怒っています。少なくとも、2つの配列値を繰り返しスワップする無限のwhileループに陥らないのはなぜですか?明白なことはさておき、それが魔法のようにループから抜け出したとしましょう。最小値を探している場合、スワップをカウントするために使用している条件下で、どのようにして正しい答えを得ることができるでしょうか。スワップの数?コードのさまざまなポイントにprintステートメントを追加して、何が起こっているのかを確認し、自分で理解しようとしましたが、混乱を招くだけです。誰かが私の無意味な天才の論理を私に教えてもらえますか?それともこれはまぐれですか?
#!/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()
whileの条件は、現在の要素が正しい位置にあるかどうかを確認します。
while arr[x] != x + 1:
ループ内の各反復で、x位置の値を正しい位置であるarr [x] -1に移動します。したがって、while内のすべての反復は、1つの要素の位置を修正します。以下の例を参照してください。
>>> i = 0
>>> a
[9, 1, 3, 10, 8, 5, 6, 2, 7, 4]
>>> #first iteration
>>> a[a[i]-1], a[i] = a[i], a[a[i] - 1]
>>> a
[7, 1, 3, 10, 8, 5, 6, 2, 9, 4]
>>> #second iteration
>>> a[a[i]-1], a[i] = a[i], a[a[i] - 1]
>>> a
[6, 1, 3, 10, 8, 5, 7, 2, 9, 4]
最初の反復は9を配列の9番目の位置(インデックス8)に移動し、最初の位置は7になります。2番目の反復は7を配列の7番目の位置(インデックス6)に移動し、最初の位置は6になります。
私はこれが十分に明確であることを願っています:)
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加