🐕

LeetCoding Challenge Oct. 15: Rotate Array

2020/10/16に公開

Java

LeetCode

tech

LeetCode October Challenge の 15 日目。

今日の問題は Rotate Array。

問題の概要

与えられた配列の要素を右に k 個ローテートした配列を求める

考え方

先日の Rotate List (連結リストを同様にローテートするやつ) の配列版ですね
誰でも容易に思いつくナイーブな解法はこちら
- O(n) (n は配列の長さ) の空間計算量を許容すれば、System.arraycopy() を 3 回ぐらい実行するやり方で実現できますね
- O(n * k) の時間計算量を許容すれば、こちらも配列全体を 1 つずつ右にシフトするのを k 回繰り返せばいいので可能ではありますね (時間制限に引っかかりそうだけど)
空間計算量 O(1) かつ時間計算量 O(n) の解法を考えてみたい…
- 配列上のあるインデックス i の値を、インデックス i + k の位置に代入してローテートを完成させる、というやり方をベースにしよう
  - インデックス i + k の位置にそのまま上書き代入してしまうと元の値が失われてしまうので、上書きする前にその値を一時変数とかに退避させておけばいいのでは？
アルゴリズムをもうちょっと具体化してみよう
1. 配列のインデックスを i = 0 として処理を始める
2. j = (i + k) % n とする
3. nums[j] の値を一時変数に退避しておき、nums[i] の値で上書き代入する
  - 二回目以降の実行では nums[i] の値は一時変数に入っているのでそれを使う
4. i = j として、i が 0 に到達するまで 1. 以降を繰り返す
具体的に nums = {0,1,2,3,4}, k = 2 のケースを例に挙げて考えてみよう
1. nums[0] の値を nums[２] ((0 + k) % n = 2) に入れる (nums[2] に入っていた値は一時変数に退避しておく)
2. (一時変数に退避した) nums[2] の値を nums[4] ((2 + k) % n = 4 に入れる (nums[4] の値は例によって一時変数に入れておく)
3. nums[4] の値を nums[1] ((4 + k) % n = 1) に入れる
4. nums[1] の値を nums[3] ((1 + k) % n = 3) に入れる
5. nums[3] の値を nums[0] ((3 + k) % n = 0) に入れる
上記のケースでは上手くいくようだ 💪
- 一方で、n = 4, k = 2 のケースにはそのまま適用できない 😢
- でも、先のアルゴリズムの初期値のインデックスを 0 と 1 それぞれについて実行すればうまくいきそうだね？
このアルゴリズムをどのケースにでも適用できるようにしてみよう！
- ローテート量 k が配列の長さ n 以上の値の場合はちょっと扱いにくいので、k = k % n として常に k < n となるようにしよう
- n と k の最大公約数 g を求めよう
- 0, 1, ..., g - 1 をそれぞれをインデックスの初期値にして、その初期値にまた戻ってくるまでの間、先のアルゴリズムを実行してみよう
なんかよさそうなアルゴリズムになったので実装してみよう！ → submit → accept 🤗
- Runtime 0ms 達成 🎉

コード

class Solution {
    public void rotate(int[] nums, int k) {
        if (nums.length <= 1) {
            return;
        }

        k = k % nums.length;
        if (k == 0) {
            return;
        }

        int gcd = gcd(nums.length, k);
        int limit = nums.length / gcd;

        for (int i = 0; i < gcd; i++) {
            int prev = nums[i];

            for (int j = 1; j < limit; j++) {
                int index = (i + k * j) % nums.length;
                int t = nums[index];
                nums[index] = prev;
                prev = t;
            }

            nums[i] = prev;
        }
    }

    int gcd(int m, int n) {
        if (n == 0) {
            return m;
        }
        return gcd(n, m % n);
    }
}

問題の概要

考え方

コード

Discussion