二つのソート済み配列の中央値を二分探索で求める方法
問題の理解
二つのソート済み配列が与えられた場合、全体の中央値を効率的に見つける必要があります。単純な方法では両方の配列をマージしてから中央値を計算できますが、これではO(m+n)の時間計算量が必要です。より効率的な解法として、二分探索を用いることでO(log(min(m,n)))の時間計算量で解くことができます。
アルゴリズムの考え方
二つの配列から、左半分の要素数 ...
7月31日 01:06 投稿
二つのソート済み配列の中央値の効率的な探索
問題概要
二つの昇順にソートされた整数配列 nums1 と nums2 が与えられます。それぞれの配列のサイズは m と n です。これら二つの配列を結合した場合の中央値を求めてください。
このアルゴリズムの時間計算量は O(log (m+n)) である必要があります。
例1:
入力：nums1 = [1,3], nums2 = [2]
出力：2.00000
解説：結合配列 = [1,2,3] 、中央値 2
アプローチ1：マージ ...
5月16日 05:19 投稿