問題
Program for array rotationにあるリストのローテーション問題。指定されたdの数分、左にローテーションさせていく問題。このページの最後にある最大公約数を使ったローテーション方法の内容を勉強。
d = 3 input: 1,2,3,4,5,6,7,8,9 ↓ output: 4,5,6,7,8,9,1,2,3
実装
最大公約数(greatest common divisor)を使うとうまくローテーションする回数、つまりローテーションする回数を管理するインデックスのiをうまく決めることができる。うん、考えた人賢すぐる。インデックスが動くイメージは画像の通り。geeksforgeeksじゃないけど、動画の解説もあった。
ループの度に集合をイメージし、各ブロックの先頭要素を正しい位置にいれる。そして、次のループで各ブロックの先頭要素の次の要素を正しい位置にいれるを繰り返す。
def gcd(a, b):
if b == 0:
return a;
else:
return gcd(b, a % b)
def leftRotate(numbers, d):
len_numbers = len(numbers)
d = d % len_numbers
n_gcd = gcd(d, len_numbers)
for i in range(n_gcd):
tmp = numbers[i]
j = i
while 1:
k = j + d
if k >= len_numbers:
k = k - len_numbers
if k == i:
break
numbers[j] = numbers[k]
j = k
numbers[j] = tmp
if __name__ == '__main__':
nums = [1,2,3,4,5,6,7,8,9]
print(nums)
leftRotate(nums, 3)
print(nums)
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[4, 5, 6, 7, 8, 9, 1, 2, 3]
