問題の説明
リストの要素をkだけ回転させます。
解法
アプローチ
入力リストが[1,2,3,4,5,6,7]でkが3の場合、要素iをkだけシフトする単純なアプローチがあります。ただし、以下のような場合に問題が発生します。
1
123456 k=2
この場合、kだけシフトすると、次のようになります。
1
2
3
4
5
6
123456
1
3
5
1
3
ここで、kの位置にジャンプして同じ要素をサイクルしてしまいます。これを防ぐために、サイクルの開始点を記録する変数initを導入し、iが初期のポイントに戻るとiを+1します。これにより同じ要素をサイクルするのを防ぎます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
# 配列の長さがkと同じ場合はnumsを返す
# 配列の長さが1の場合はそのまま返す
if len(nums) == k or len(nums) == 1:
return nums
i = 0
init = i
before = nums[i-(k%len(nums))]
cnt = 1
while cnt <= len(nums):
# 一周回ってまた自分自身に戻り、かつ残りの要素がある場合、iを+1する
if i == init and cnt != 1:
i += 1
init += 1
before = nums[i-(k%len(nums))]
temp = nums[i]
nums[i] = before
before = temp
i = (i+k)%len(nums)
cnt += 1
この解法の時間複雑度と空間複雑度は次のとおりです。
- 時間複雑度：O(N)
- numsをループするため、時間複雑度はO(N)です。
- 空間複雑度：O(1)
- 追加のスペースは使用されていません。