ゼロから始めるLeetCode Day92 「4. Median of Two Sorted Arrays」

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

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

次回
まだ

Twitterやってます。

問題

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番目に小さい数を返すための関数です。

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

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