LeetCodeはゼロブラシから(4.Median of Two Sorted Arrays)
3650 ワード
この問題は私がleetcodeを塗って出会った最初の難易度がHardの問題で、筆者は大学でアルゴリズムの授業を勉強していたときに似たような問題に触れたことがありますが、時間が長くなった上に、当時このような問題型について深く理解していなかったので、やり方を忘れました.いくつかの技術系ブログを調べた後、当時の考えを取り戻した.
タイトルは以下の通りです.
There are two sorted arrays nums1and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
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
この問題の入力は2つのsortedされた配列であり,2つの数のグループが合併した中位数を返すことを要求し,時間複雑度はO(log(m+n))を要求する.
本題は時間の複雑さの要求を考慮しなければ,mergeSortを容易に考えることができる.2つの並べ替えられた配列を1つの配列にまとめることを1回のmergeと呼びます.簡単です.2つのグループを指すヘッダポインタを2つ設定し、より小さな要素を取るたびに新しい配列に追加し、2つの配列の数が取り出されるまで後方に移動します.(本題はこのような思想で時間の複雑さの要求に合わない) 二分検索の考え方は、時間の複雑さをO(log(m+n)) に下げることができる.
mergeSortでmergeを1回適用し、必要な中位数を見つけます.この方法は簡単です.ここではコードを列挙しません.しかし,この方法はO(log(m+n))時間の複雑さの要求に合致しない.
Binary Discardは筆者自身がつけた名前で、Leetcode 4 Median of Two Sorted Arraysの原文の解釈は英語です.ここで簡単に訳します.
ここで問題は,2つのsorted配列のk番目の小さい要素を探すことに汎化する.Aのk/2番目とBのk/2番目の要素(すなわちA[k/2-1]とB[k/2-1]を比較する)を比較すると、(ここでは、kが偶数であり、両配列の要素個数がk/2以上であることが好ましい.非理想の場合、以下の詳細処理により、結果は同じである)A[k/2-1]=B[k/2-1]A[k/2-1]B[k/2-1]の第1のケースが存在する.目標値は、ちょうどA[k/2-1]またはB[k/2-1]である.AとBのmergeSortの後の配列を明確に表す表を用いることができます.
1th : (k-2)th
(k-1)th
kth
(k+1)th : last
A[0:k/2-2] and B[0:k/2-2]
A[k/2-1]
B[k/2-1]
A[k/2:last] and B[k/2:last]
2つ目のケース:A[0:k/2-1]のすべての要素は、AB結合配列の最初のk個の最小要素にある.言い換えれば、A[k/2−1]は、AB結合配列のk番目に小さい要素よりも小さい.この点は反証法で証明できますが、よく理解できます.ここでは証明しません.したがって、A[0:k/2-1]のすべての要素を破棄することができます.**3つ目のケース:**とケース2は同じです
次にedge condition,すなわち再帰関数の終了条件を考える. AまたはBのいずれかの配列が空の場合、A[k-1](またはB[k-1]) を返す. k=1のとき(A,Bともに空ではない)、min(A[0]、B[0]) を返す. A[k/2-1]=B[k/2-1]の場合、そのうちの1つを返すことができる .
残りは細部の処理です.操作を容易にするために、mは常にn より小さい. Aで選択した要素の数を A、B要素の個数とm+nが奇数であれば、中位数は(m+n)/2+1の最小を探す数である.A,B元素の個数とm+nが偶数である場合、中位数は(m+n)/2番目と(m+n)/2+1番目の最小数を探す平均数 である.
具体的なC++コードは以下の通りです.
タイトルは以下の通りです.
There are two sorted arrays nums1and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
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
タイトル
この問題の入力は2つのsortedされた配列であり,2つの数のグループが合併した中位数を返すことを要求し,時間複雑度はO(log(m+n))を要求する.
知識の要点
問題を解く構想.
Approach 1: MergeSort
mergeSortでmergeを1回適用し、必要な中位数を見つけます.この方法は簡単です.ここではコードを列挙しません.しかし,この方法はO(log(m+n))時間の複雑さの要求に合致しない.
Approach 2: Binary Discard
Binary Discardは筆者自身がつけた名前で、Leetcode 4 Median of Two Sorted Arraysの原文の解釈は英語です.ここで簡単に訳します.
ここで問題は,2つのsorted配列のk番目の小さい要素を探すことに汎化する.Aのk/2番目とBのk/2番目の要素(すなわちA[k/2-1]とB[k/2-1]を比較する)を比較すると、(ここでは、kが偶数であり、両配列の要素個数がk/2以上であることが好ましい.非理想の場合、以下の詳細処理により、結果は同じである)A[k/2-1]=B[k/2-1]A[k/2-1]
1th : (k-2)th
(k-1)th
kth
(k+1)th : last
A[0:k/2-2] and B[0:k/2-2]
A[k/2-1]
B[k/2-1]
A[k/2:last] and B[k/2:last]
2つ目のケース:A[0:k/2-1]のすべての要素は、AB結合配列の最初のk個の最小要素にある.言い換えれば、A[k/2−1]は、AB結合配列のk番目に小さい要素よりも小さい.この点は反証法で証明できますが、よく理解できます.ここでは証明しません.したがって、A[0:k/2-1]のすべての要素を破棄することができます.**3つ目のケース:**とケース2は同じです
次にedge condition,すなわち再帰関数の終了条件を考える.
残りは細部の処理です.
pa = min(k/2, m);で表します.Bで選択した要素の数をpb = k - pa;で表します.このようにすれば、m具体的なC++コードは以下の通りです.
class Solution {
public:
int min(int a, int b){
return a nums1, vector nums2){
int m = nums1.size(), n = nums2.size();
//assume m <= n;
if (m > n)
return findKth(k, nums2, nums1);
//2 terminate conditions
if (m == 0)
return nums2[k-1];
if (k == 1)
return min(nums1[0], nums2[0]);
//two parts and discard one
int pa = min(k/2, m);
int pb = k - pa;
if (nums1[pa-1] > nums2[pb-1]){
nums2.erase(nums2.begin(), nums2.begin()+pb);
return findKth(k-pb, nums1, nums2);
}
else if (nums1[pa-1] < nums2[pb-1]){
nums1.erase(nums1.begin(), nums1.begin()+pa);
return findKth(k-pa, nums1, nums2);
}
else
return nums1[pa-1];
}
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int cnt = nums1.size() + nums2.size();
if (cnt % 2 == 1)
return (double)findKth(cnt/2+1, nums1, nums2);
else
return (findKth(cnt/2, nums1, nums2) + findKth(cnt/2+1, nums1, nums2)) / 2.0;
}
};