🤖
LeetCode: 189. Rotate Array をGoで解く

2024/09/23に公開
LeetCodeの問題を解いたら、記録することにした。Goで解く。

 問題189. Rotate Array
numsという数字の配列が与えられる。それをk回右方向にベルトコンベアー的に動かした結果を返すというもの。なお、一番右の要素を右に動かすと、配列の一番左に移動する。
難易度はmediumにカテゴライズされる。

 制約1 <= nums.length <= 105

-231 <= nums[i] <= 231 - 1

0 <= k <= 105

 解いてみる
 ぱっと思いついた解き方ぱっと思いついたのは、右に1つ動かすという操作をk回繰り返す。

図のようなイメージ。

コードにすると以下。
solution.go
func rotate(nums []int, k int) {
	// k回右にローテーション
	for i := 0; i < k; i++ {
		rotateOneTime(nums)
	}
}

// 右方向にすべての要素を1回ローテーション
func rotateOneTime(nums []int) {
	var tmp int
	for i := 0; i < len(nums); i++ {
		if i == 0 {
			tmp = nums[0]
			nums[0] = nums[len(nums)-1]
			continue
		}
		t := nums[i]
		nums[i] = tmp
		tmp = t
	}
}
しかし、これを実行してもPassしない。kが54944でnumsの長さが100000のテストケースでタイムアウトする。

空間計算量はO(1)なので良さそうだが、k * len(nums)の回数分のループが発生するので、kやlen(nums)が大きくなればなるほど時間がかかってしまう。O(k * n)。

いずれにせよ、ループの回数を減らす必要がありそう。
一応、フォローアップに「Could you do it in-place with O(1) extra space?」とあるので、与えられたnums以外の配列やslice、mapは使わないようにしたい。kとlen(nums)がケースごとに変わるので、この制約を守りつつ考えるのはかなり頭を消費する。

 解き方いくつか別解はあるみたいだが、一番しっくりきたのは以下。ローテーションという先入観を取っ払わないと思いつけない。
与えられたnums全体を逆にする。

↓

最初のk個を逆にする。

↓

後ろのlen(nums) - k個も逆にする。
これをGoで表してみた。
solution.go
func rotate(nums []int, k int) {
	k %= len(nums)
	reverse(nums, 0, len(nums)-1)
	reverse(nums, 0, k-1)
	reverse(nums, k, len(nums)-1)
}

func reverse(nums []int, startIdx, endIdx int) {
	var tmp int
	for i := startIdx; i < endIdx; i++ {
		tmp = nums[endIdx]
		nums[endIdx] = nums[startIdx]
		nums[startIdx] = tmp
		startIdx++
		endIdx--
	}
}
k %= len(nums)がトリッキー。これは、len(nums) < kのときに、
ローテーションの回数が過剰になるのをやめるため

index out of rangeを防ぐため
のもの。
ローテーション回数が過剰になるというのは以下の図のイメージ。kが大きいがゆえに短いnumsを何回もグルグルローテーションすると、同じ結果が発生することがあるということである。なので、ローテーション結果がはじめて期待するものと一致する値にkを合わせてしまっても（小さくしてしまっても）、結果としてはOKとなる。

また、numsへのインデックスアクセスをkを使って行うので、len(nums) < kだと、Goだとpanicになる。多分他の言語でも基本だめだと思う。なので、kを「len(nums)より小さい」かつ、「ローテーション結果が変わらない」ものに変更してあげる必要がある。
上記コードを実行すると、ちゃんとPassした。
Runtime 18ms (Beats 93.47%)
Memory 7.78mb (Beats 52.79%)
そして、len(nums)に対する一重ループをしているのと、numsをin-placeでreverseしているので、
Time Complexity O(N)
Space Complexity O(1)
となった。
問題

制約

解いてみる

ぱっと思いついた解き方

解き方

Discussion
