LeetCode daily 1920. Build Array from Permutation

【LeetCode #1920】Build Array from Permutation

はじめに

GW が終わります...
今日の daily は easy でしたので簡単に感じた方も多いかもしれませんが，早速やっていきましょう．

問題概要

与えられた重複のない 0~nums.length-1 の値を持つ配列に対して，下記を満たす配列を返す．

• ans[i] = nums[nums[i]]

例

nums = [2, 0, 1]
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]]]
    = [nums[2], nums[0], nums[1]] = [1, 2, 0]

解法①：実直に配列に格納パターン

単純に，ans[i] = nums[nums[i]] を満たす配列を作成すれば良いので，あらかじめ ans を用意しておき，forループを行う．

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        ans = [0] * len(nums)
        for i, n in enumerate(nums):
            ans[i] = nums[nums[i]]
        return ans

問題なく AC になります．
ただ，問題文にこのような文言が！

Follow-up: Can you solve it without using an extra space (i.e., O(1) memory)?

解法②：O(1) での解法（in-place）

解法①では，O(n) のメモリ使用量なので，これを O(1) に書き換えます．

概要

nums[i] に古い値と新しい値の両方の情報を持たせます．（直接書き換えていくと，nums が破壊されるため）
その後，新しい値のみ抽出します．

アプローチ

nums は 0~n-1 の順列で構成される長さ n の配列．
各要素に，n 進数の1桁目=古い値，2桁目=新しい値を格納するイメージ．
これにより，nums[i] % n で古い値，nums[i] // n で新しい値が取得できるようになる．
具体的には nums[i] += n * (nums[nums[i]] % n) で2つの情報を保持する．

1. nums[i] % n で古い値が取得できる理由

\displaylines{
nums[i] += n * (新しい値) \\
nums[i] = 元の値 + n * 新しい値 \\ 
nums[i] \% n = (元の値 + n * 新しい値) \% n = 元の値
}

となり、必ず元の値だけが抽出される．
2. nums[i] // n で新しい値が取得できる理由

\displaylines{
nums[i] = 元の値 + n * 新しい値 \\ 
nums[i] // n = 新しい値
}

が成立する（整数除算）.

具体例

nums = [0, 2, 1, 5, 3, 4]で，i = 4 の時

1. n = 6， nums[i] = 3， nums[nums[i]] = 5
2. nums[i] += 6 * (5 % 6) = 33
3. nums[i] %= 6 = 3 = 古い値
4. nums[i] //= 6 = 5 = 新しい値

実装

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n):
            nums[i] += n * (nums[nums[i]] % n)
        for i in range(n):
            nums[i] //= n
        return nums

実装はこうなります．

まとめ

今回は easy 問題で，配列の中身を入れ替える問題を解きました．
普通に解けば簡単な問題ですが，in-place で解こうとすると，結構難しい問題だったのではないでしょうか？
また次回，別問題解説します！お楽しみに :)

おまけ

TypeScript だとこうなります．
解法①

function buildArray(nums: number[]): number[] {
    let ans: number[] = Array(nums.length).fill(0);
    for (let i: number = 0; i < nums.length; i++){
        ans[i] = nums[nums[i]];
    }
    return ans
};

解法②

function buildArray(nums: number[]): number[] {
    const n: number = nums.length
    for (let i: number = 0; i < n; i++){
        nums[i] += n * (nums[nums[i]] % n);
    }
    for (let i: number = 0; i < n; i++){
        nums[i] = ~~(nums[i] / n);
    }
    return nums
};