ゼロから始めるLeetCode Day57 「35. Search Insert Position」

概要

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

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

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

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

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

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day56 「1480. Running Sum of 1d Array」
次回
ゼロから始めるLeetCode Day58 「20. Valid Parentheses」

Twitterやってます。

問題

35. Search Insert Position

難易度はEasy。

とあるアルゴリズムを学ぶのに良い問題だと思ったので記事を書きました。

問題としては、ソートされた配列とターゲットの値が与えられたます。
ターゲットが見つかった場合はそのインデックスを返します。見つからなかった場合は、それが順番に挿入された場合のインデックスを返すような、アルゴリズムを設計してください、というものです。

なお、配列内に重複がないと仮定しても構いません。

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0

解法

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) -1
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return low
# Runtime: 56 ms, faster than 49.71% of Python3 online submissions for Search Insert Position.
# Memory Usage: 14.6 MB, less than 16.72% of Python3 online submissions for Search Insert Position.

知っている人が見たらわかると思いますが二分探索の問題です！

Pythonではライブラリにbisectがあるのでそちらを使って簡単に書くこともできるのですが、原理原則を知ってかける能力が大事だと思うので書いてみました。

知っておくとどこかで助かるかも・・・？

今回はここまで。
お疲れ様でした。