Rotate Array
整数の配列 nums と数値 k が与えられます。配列を右に k ステップ回転させます。1ステップで各値は右に1つ移動し、最後の値は先頭に回り込みます。回転後の配列を返してください。
k は配列の長さよりはるかに大きい場合があります。
関数
- numsinteger-array
- 回転させる整数の配列
- kinteger
- 右に回転するステップ数
- 戻り値integer-array
- nums を k ステップ右に回転
制約
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 1040 ≤ k ≤ 109
例
- 入力
- nums = [4, 9, 1, 6, 3]k = 2
- 出力
- [6, 3, 4, 9, 1]
- 説明
- 右に2つ移動すると、最後の2つの値である6と3が先頭に回ります。残りの3つの値は順序を保ったまま右に2つ移動します:
[6, 3, 4, 9, 1]。
- 入力
- nums = [10, 20, 30]k = 7
- 出力
- [30, 10, 20]
- 説明
- 3ステップ進むごとに、長さ3の配列は出発点に戻るため、7ステップは7 mod 3 = 1ステップと同じように作用します。1ステップで30が先頭に移動します。
- 入力
- nums = [-5, 8]k = 4
- 出力
- [-5, 8]
- 説明
- 4 mod 2 = 0 なので、4 ステップ後にはすべての値が元の位置に戻り、配列は変化しません。
発展問題
各値をそのまま (i + k) mod n に移し、押し出された値をさらに次へ運ぶことで、その場で回転できますか？その場合、サイクルはいくつできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
長さ
nの配列は、nステップ後に元の順序に戻ります。kが10^9の場合、実際に意味があるのは何ステップですか？回転後、最後の
k mod n個の値が配列の先頭になり、残りの値がそれぞれ元の順序のまま続きます。インデックスiの値はどこに移動しますか？配列全体を反転すると、最後のブロックが先頭に来ますが、両方のブロックが逆順になります。それぞれのブロックをもう一度反転して、順序を元に戻します。各反転では、2つのインデックスが互いに向かって進みます。
解説
nステップ進むごとに配列は元の位置に戻るため、まず最大で 10^9 となる k を k mod n に減らします。その後、各値を2つ目の配列の最終インデックスに直接書き込むか、3回の反転と O(1) の追加メモリを使って配列内で同じ結果を実現します。
各値を新しいインデックスにコピーする
考え方
k回の操作後、インデックスiの値は(i + k) mod nの位置に移るので、操作を実行せずにその位置へ直接書き込みます。まずkをk mod nにします。n回の回転ではすべての値が元の位置に戻るため、k = 7、n = 3の場合、残るのは1回の操作だけです。
1回の走査ですべてのn個の値を配置できます。時間計算量はO(n)、結果を保存するためのメモリ計算量はO(n)です。この方法ではnums自体に書き込むことはできません。まだ移動していない値が、書き込みによって上書きされてしまうためです。
アルゴリズム
nにnumsの長さを設定し、kをk mod nに置き換えます。- 長さが
nの結果配列を作成します。 - 各インデックス
iについて、nums[i]をresult[(i + k) mod n]に格納します。 - 結果を返します。
def rotate(nums, k):
n = len(nums)
k %= n # a full turn of n steps changes nothing
result = [0] * n
for i in range(n):
result[(i + k) % n] = nums[i]
return resultその場での3回の反転
考え方
配列を、最初の n-k 個の値である A と、最後の k 個の値である B に分割します。回転後の配列は、元の順序のままの各ブロックを並べた、B の後に A が続く配列です。配列全体を逆順にすると、ブロックの順序と各ブロック内の順序の両方が反転するため、B が先頭に来ますが、読み順は逆になり、A も同様です。各ブロックをもう一度逆順にすると、ブロック内の順序が元に戻ります。
[4, 9, 1, 6, 3] と k = 2 の場合、すべてを逆順にすると [3, 6, 1, 9, 4] になり、最初の2つを逆順にすると [6, 3, 1, 9, 4] になり、最後の3つを逆順にすると [6, 3, 4, 9, 1] になります。
各値が入れ替えられるのは最大2回なので、時間計算量は O(n) で、追加メモリは数個のインデックス変数です（Rでは、逆順化ヘルパーがベクトルを変更するとコピーが発生するため、O(n) です）。
アルゴリズム
nをnumsの長さに設定し、kをk mod nに置き換えます。- インデックス 0 から
n-1までの配列全体を逆順にします。 - インデックス 0 から
k-1までの最初のブロックを逆順にします。 - インデックス
kからn-1までの2番目のブロックを逆順にします。 numsを返します。
def rotate(nums, k):
n = len(nums)
k %= n # a full turn of n steps changes nothing
def reverse(left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
reverse(0, n - 1) # the last k values come to the front, backwards
reverse(0, k - 1) # put the front block back in order
reverse(k, n - 1) # and the back block
return nums
落とし穴と境界ケース
k mod nを忘れる。k = 10^9の場合、1ステップずつ回転させても終わらず、最初のk個の値を逆順にすると、配列の末尾を大きく越えて読み取ってしまいます。- 剰余を使わずにスライスする。Pythonでは、
k = 7、n = 3のとき、nums[-k:] + nums[:-k]は配列をそのまま返します。どちらのスライスも配列の端で止まるためです。 - 逆順にする順序を間違える。先に2つのブロックを逆順にし、最後に配列全体を逆順にすると、左回転になります。
- ブロックの境界でオフバイワンになる。最初のブロックはインデックス
k-1で終わり、2つ目はkから始まります。1から数えるLuaとRでは、ブロックは1..kとk+1..nです。
よくある質問3
配列の回転の時間計算量はどれくらいですか？
コピー方式と3回の反転のどちらもO(n)です。各値が定数回だけ移動するためです。最初にkをk mod nで小さくしておけば、非常に大きなkの影響を防げます。代わりに一度に1ステップずつ回転すると、コストはO(n × k)になります。
k が配列の長さより大きい場合、どうなりますか？
n回ごとに配列は元の順序に戻るため、重要なのはk mod n回だけです。[10, 20, 30]を7回回転させることは、1回回転させるのと同じで、その結果は[30, 10, 20]になります。kがnの倍数の場合、配列は変化しません。
配列を左に回転させるにはどうすればよいですか？
kだけ左に回転させることは、n - (k mod n)だけ右に回転させることです。反転を使う場合は、最初のk mod n個の値を反転し、次に残りを反転し、最後に配列全体を反転します。どちらも時間計算量はO(n)です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def rotate(nums, k):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [4, 9, 1, 6, 3] k = 2
期待される出力
[6, 3, 4, 9, 1]