[leetCode] Top Interview 150: Rotate Array

リンク

https://leetcode.com/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150

概要

• 整数配列numsと、回転する回数kが与えられる
• numsを指定された回数右に回転させる

解法

先に、シンプルかつ分かりやすい解説があったので共有。
https://leetcode.com/problems/rotate-array/solutions/1730142/java-c-python-a-very-very-well-detailed-explanation/?envType=study-plan-v2&envId=top-interview-150

かんたんに解説すると、

• 前提として、k = nのときとk = n+nums.lengthのときの結果は一緒
  • k %= nums.lengthとして考えてよい
• 配列を回転させた結果は、以下の手順で取得できる
  1. 配列を二分するラインを見つける（今回はk）
  2. 左右の配列を反転させる
  3. 全体を反転させる

という感じ。

class Solution {
    // main
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, (nums.length - 1) - k);
        reverse(nums, nums.length - k, nums.length - 1);
        reverse(nums, 0, nums.length - 1);
    }

    public static void reverse(int nums[], int start, int end) {
        while(start < end) {
            int w = nums[start];
            nums[start] = nums[end];
            nums[end] = w;

            start++;
            end--;
        }
    }
}

あとがき

最初に提出したとき、はちゃめちゃにメモリ使用率が高くて驚いた。

「おかしいな...空間計算量はO(1)だし...」とか思いつつ、二回目を提出するとめっちゃ下がった。

どうやら提出によってテストケースが違うっぽい。