概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day91「153. Find Minimum in Rotated Sorted Array」

Twitterやってます。

技術ブログ始めました！！
技術はLeetCode、Django、Nuxt、あたりについて書くと思います。こちらの方が更新は早いので、よければブクマよろしくお願いいたします！

お知らせ

Day 100でQiitaでの投稿はひとまず区切りを付けようかと思います。
タグの記事が僕の記事ばかりになってしまうのもいかがなものかと思いましたし、他に有益な情報を提供している方の邪魔になってしまうこともあると考えたので、こうすることにしました。
至らない部分は多々ありましたが、今までお付き合い頂きありがとうございました。

問題を解いて記事を書く、というのは上記の個人ブログで続けるつもりですし、興味ある方はたまにそちらを覗いていただけると嬉しいです。
Twitterの方のアカウントはほとんど更新通知用と化しているので、Leetcodeを解く記事について気になる方はそちらも合わせてフォローいただくと良いかもしれません。

問題

4. Median of Two Sorted Arrays
難易度はHard。

問題としては、サイズmとnの2つのソートされた配列nums1とnums2がある。2つの並べ替え配列の中央値を求めよ。
なお、全体の実行時間の複雑さは，O(log (m+n))でなければならず、nums1とnums2はどちらも空ではないと仮定してもよい。

Example 1:

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

解法

O(log(m+n))である、ということは二分探索が使えますね。
ただ、難易度がHardということで、扱うリストが二つになっています。
これで書くコードの量が増えますし、書く量が増えるということは凡ミスも増える可能性が高くなります。
そして、二つとも同じ大きさのリストとは限らないのでその点もきちんと頭に入れておきましょう。

class Solution:
    def obtain_kth_num(self, nums1, nums2, k):
        nums1_len, nums2_len = len(nums1), len(nums2)
        nums1 = [-2**31] + nums1 + [2**31-1]
        nums2 = [-2**31] + nums2 + [2**31-1]
        left, right = max(0, k-nums2_len), min(nums1_len, k)
        while left <= right:
            i = (left+right) // 2
            j = k - i
            if nums1[i] > nums2[j+1]:
                right = i - 1
            elif nums2[j] > nums1[i+1]:
                left = i + 1
            else:
                return max(nums1[i], nums2[j])

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums_len = len(nums1) + len(nums2)
        mid = self.obtain_kth_num(nums1, nums2, (nums_len+1)//2)
        if nums_len % 2 == 0:
            mid = (mid+self.obtain_kth_num(nums1, nums2, (nums_len+1)//2+1)) / 2.0
        return mid
# Runtime: 116 ms, faster than 35.51% of Python3 online submissions for Median of Two Sorted Arrays.
# Memory Usage: 13.9 MB, less than 92.38% of Python3 online submissions for Median of Two Sorted Arrays.

DFSなどと同様に別に関数を実装してからメインで呼び出す、という形式を取りました。
-2**31や2**31-1というのはPython3にはlong型が存在しないためこういった方式を取っている、というのを以前も解説した気がします。

obtain_kth_num関数は与えられたnums1とnum2を入力として受け取り，配列のk番目に小さい数を返すための関数です。

なお、二分探索をする上で根底となる考え方はこの動画を参考にしました。
こういう動画を作れるくらい強くなりたい・・・

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