ゼロから始めるLeetCode Day1 「1389. Create Target Array in the Given Order」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

Twitterやってます。

問題

1389. Create Target Array in the Given Order

問題としては、
・返す配列(array)は最初は空。
・nums[i]とindex[i]が与えられて、indexの場所にnumsを挿入する。
・numsとindexの要素がなくなるまで繰り返す。
最後に配列(array)を返して終わり。

想像つかない場合は実際に読んでみてください。

class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        target = []
        for i in range(len(nums)):
            target.insert(index[i],nums[i])
        return target

# Runtime: 36 ms, faster than 36.25% of Python3 online submissions for Create Target Array in the Given Order.
# Memory Usage: 13.9 MB, less than 100.00% of Python3 online submissions for Create Target Array in the Given Order.

ぱっと思いついたのはこれ。
numsとindexの要素数は同じという前提がConstraintsに書いてあったので、それなら一回for文で回してその要素数をそれぞれinsert関数の中に入れてしまえばいいねというもの。
ただ、速くなく、ありきたりすぎる気がする。

他に考えついたのはwhile文で書くことだが、
Pythonを速くしたいときにやったことによると、Pythonではwhile文の方が遅いようだ。

なお、一応念のために書いて実行してみた。

class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        target = [0]*len(index)
        j = 0
        while j < len(index):
            target.insert(index[j], nums[j])
            j += 1
        return target[:len(nums)]

# Runtime: 36 ms, faster than 36.25% of Python3 online submissions for Create Target Array in the Given Order.
# Memory Usage: 13.8 MB, less than 100.00% of Python3 online submissions for Create Target Array in the Given Order.

…あれ？
同じやんけ。
むしろメモリの使用量ちょっと少ないし。

ま、まぁ一旦ひとまずこれはおいておいて、大幅に速度が上がるものではありませんでした。

私が思いつかなかったものとしては、zip関数を使ったもの、スライスを使ったものです。

zip関数は、公式ドキュメントに記載されている通り、

それぞれのイテラブルから要素を集めたイテレータを作ります。
この関数はタプルのイテレータを返し、その i 番目のタプルは引数シーケンスまたはイテラブルそれぞれの i 番目の要素を含みます。このイテレータは、入力イテラブルの中で最短のものが尽きたときに止まります。単一のイテラブル引数が与えられたときは、1 要素のタプルからなるイテレータを返します。引数がなければ、空のイテレータを返します。

というもので、

hoge = [1,2,3,4,5]
foo = [6,7,8,9,10]
bar = zip(hoge,foo)
list(bar)
[(1,6),(2,7),(3,8),(4,9),(5,10)]

以上のような動きをします。

なお、これを使っているものとしては、こちら。

class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        res = []
        for i, v in zip(index, nums):
            res.insert(i, v)
        return res
# Runtime: 28 ms, faster than 90.08% of Python3 online submissions for Create Target Array in the Given Order.
# Memory Usage: 13.8 MB, less than 100.00% of Python3 online submissions for Create Target Array in the Given Order.

速い！
これ以降は似た問題が出た場合にはzip関数を使った方が良さげですね。

お疲れさまでした、また解いて記事をかけたらなと思います。

せっかくだし空いてる時間を使ってPythonのfor文とwhile文の速度に関する記事も書いてみようかな・・・