二つのソート済み配列から中央値を探索する
与えられた二つの昇順にソートされた配列 nums1（長さ m）と nums2（長さ n）から、これらを結合した際の中央値を特定する方法について解説します。
この問題の最適解は通常 O(log (m+n)) の時間計算量が求められますが、ここではまず、より直感的で実装しやすい O(m+n) のアプローチを紹介します。
問題の詳細と制約
配列 nums1 と nums2 はそれぞれ昇順にソートされてい ...
9月7日 01:37 投稿
二つのソート済み配列の中央値を二分探索で求める方法
問題の理解
二つのソート済み配列が与えられた場合、全体の中央値を効率的に見つける必要があります。単純な方法では両方の配列をマージしてから中央値を計算できますが、これでは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 投稿