yono.dev

LeetCodeがんばるぞ

189. Rotate Array

LeetCode

問題概要

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

integerの配列を右にk回ローテートする。

問題URL：https://leetcode.com/problems/rotate-array/description/

解法1

ブルートフォースな解法。
Beats 5.05% 激遅

一つずつ右にローテートするのをk回行う。

func rotate(nums []int, k int)  {
    size := len(nums)
    for k > 0 {
        tail := nums[size-1]
        for i := size - 1; i > 0; i-- {
            nums[i] = nums[i-1]
        }
        nums[0] = tail
        k--
    }
}

解法2

time O(n) の解法。
Beats 92.37% まずまず。

スライスを先頭からループして、各要素を右にkローテートする。
解法1では右に1ローテートするのをk回繰り返していたが、今回は一気にkローテートしている。

nums のcopyして保持しているのは、ローテートするときに、元々ローテート先にあった要素がわからなくなるから。

func rotate(nums []int, k int)  {
    size := len(nums)
    if size == k {
        return
    }
    backup := make([]int, 0, size)
    backup = append(backup, nums...)

    for i := 0; i < size; i++ {
        rotatedIdx := (k % size) + i
        if rotatedIdx >= size {
            rotatedIdx = rotatedIdx - size
        }
        nums[rotatedIdx] = backup[i]
    }
}

解法3

Time O(n) Space O(1) の解法。

要素の反転（リバース）をうまく使えば良いらしい。

func rotate(nums []int, k int) {
    size := len(nums)
    // k が len(nums) より大きいときを考慮した処理
    // 【詳細】
    // k = len(nums) のとき要素は一周して元の位置に戻る。
    // したがって、k > len(nums)の場合は `k % size`（余り）回ローテートすれば良い。
    // len(nums) [f:id:nomuyoshi0111:20240328005046p:plain]>= k の場合は `k % size` = k なので、常に k = k % size としても問題ない。
    k = k % size
    if k == 0 {
        return
    }

    reverse(nums, 0, size-1)
    reverse(nums, 0, k-1)
    reverse(nums, k, size-1)
}

func reverse(nums []int, start, end int) {
    for end > start {
        nums[start], nums[end] = nums[end], nums[start]
        start++
        end--
    }
}

パッと理解できなかったので図を書いた。

やりたいこと

例: nums = [1,2,3,4,5,6,7], k = 3 のとき

感想

解法3は思いつかず、submissionsを見た。

思いつかなかったし、解答を見てもすぐ理解できなかったけど、「やりたいこと」の画像の図を書いたときにイメージがついた。

紙に図を書きながら取り組むことが大切 だと感じた。

良い教訓を得られて良かった。

ちなみに