leetcode第四題Median of Two Sorted Arrays
私はまたleetcodeの勉強を続け始めました.第4題はずっと前からやっていました.問題は、2つのシーケンスが与えられ、2つのシーケンスが統合された中位数が要求されることである.キー:アルゴリズム複雑度T(n)=O(log(m+n))この問題の鍵は複雑さの制限にあり、この制限があれば、この問題は5つ星の難易度になる.
残念なことに、私は解決策を見つけただけです.集計法(鬼の集計ソートのような考え方で、以下に説明します)です.この方法の時間複雑度はO(m+n)ですが、時間複雑度のもっと簡単な方法があることに気づきました.二分検索のように、頭が大きくなっています.今はまだはっきりしていません.少しずつ来てください.
まず最も難しい方法を話しましょう:以下は私が抜粋したアルゴリズムの基本原理で、私が見た後も雲の中で霧の中で、私は何度も見てやっと理解して、この方法を考え出した人は本当にです.牛.
この解法の大まかな考え方は簡単で、A配列の中間要素とB配列の中間要素を比較して、小さい要素が存在する配列の前半と大きい要素が存在する配列の後半を削除することです.再帰する.
実は以上の解法を正しく実現するにはtrickyのほうがいいです.多くの境界状況にかかわる必要があるので、一つ一つ説明します.
最初のステップは、k番目の小さな要素findKthSortedArraysを探すことにテーマを変更する必要があります.(ここでkは1から計算)
なぜなら,medianに執着すると,要素の半分程度を削除して形成されたサブ問題では,依然としてmedianを探すことが保証されにくいからである.メディアの前または後を探すようになる可能性があります.
(この問題をよく考えればこの言葉が理解できる)
k番目の小要素に変更する利点は,削除した要素を考慮し,サブ問題でkの値を絶えず変更できることである.
(例えば、本来私たちが探しているメディアは5番目の数で、前の2つの数を削除すると、サブ問題では5-2=3番目の数を探すようになります)
A,B配列の総数のパリティを考慮するとfindKthSortedArraysを呼び出す問題に変換される.
第二部:findKthSortedArraysの実現
(一)まず,A配列がB配列より短いことを規定する.
このような処理の利点は,我々が必要とする(k−1)/2位置がある配列の全長よりも大きい可能性があり,Aが短いことを規定した後,Aを超える長さを考慮するだけで,状況を分けて議論する必要がないことである.
ここでは、なぜk/2ではないのかを考慮する必要があります.k/2±1?(k-1)/2
私の考えは次の通りです.
k=1,2の場合は、最初の2つの要素を比較する必要があるため、下に0と表示されます.
k=3,4の場合、1番目の要素を比較する必要があるため、下に1と表示されます.
まとめて得た.
(二)次に、特殊な状況を処理する.
(1)A配列が空の場合,B配列のk番目の要素を返す.
(2)k=1の場合、A[0]、B[0]の中のあの
(3)次に2つの状況に分けます.
(k-1)/2位置はA配列の長さを超えていますか?
(1)超えるとA配列の代表Acandiが最後の要素A[m-1]、Bの代表BcandiがB[k-m-1]となる
(a)Acandi==Bcandiであれば、ちょうどk-2個の要素がAcandi、Bcandiより小さいので、k番目の要素がAcandi/Bcandi
(b)Acandi>Bcandiでは、最大でm-1+k-m-1=k-2個の要素だけがBcandiよりも小さいので、Bcandiを含む以前のk-m個のB配列要素はk番目の数ではないに違いないので、削除すると、サブ問題はk-(k-m)番目の要素を探すことになる
(c)Acandi(2)超えなければA配列の代表AcandiがA[(k-1)/2]、Bの代表BcandiがB[(k-1)/2]
(a)Acandi==Bcandiで、(k-1)/2+(k-1)/2=k-1の要素がAcandi、Bcandiより小さいので、k番目の要素がAcandi/Bcandi
等しくなければ,Acandi,Bcandi自身が取捨選択する必要があるかどうかについては分析に注意する.
いくつかの例を挙げて簡単に分析すると,kが奇数の場合,小さなcandidateを残し,大きなものを捨てる必要があることが容易に分かった.
kが偶数の場合、大きなcandidateを残し、小さいものを捨てる必要があります.
(b)Acandi > Bcandi
(b.1)kは奇数であり、Bcandiを保持し、Bcandiの前の(k-1)/2個の要素を削除し、AおよびAの後ろの要素(Aの前(k-1)/2個の要素を保持する)を削除する
(b.2)kは偶数で、Acandiを保持し、Bcandiおよび前の(k-1)/2+1個の要素を削除し、A後の要素(A中の前(k-1)/2+1個の要素を保持する)を削除する
(c)Acandi < Bcandi
ハハ~上も頭が痛いかもしれませんね~後で私はこの問題をもっとはっきり説明できる文章を見つけました:
中心思想は:この2つの配列nums 1とnums 2はそれぞれ2つの部分に分かれている.
nums 1[0......pa-1]およびnums 1[pa......s 1-1](nums 1長s 1)nums 2[0......pb-1]およびnums 2[pb......s 2-1](nums 2長s 2)
ここでpa+pb=kは,アルゴリズム導論においてpa=pb=k/2で議論される(そこではまず1つの配列を2つの並べられた等しい長さの配列に分けるためである)が,ここで実際にコードを書く際には配列長がk/2を超えない場合,を考慮する必要がある.
最後にmedianof two sorted arraysから非常に良い方法を見た.原文は英語で説明されていますが、ここでは中国語に翻訳します.この方法の核心は,中位数が実際には(m+n)/2番目の小さい数であるように,k番目の小数点を探す問題(2つの元のシーケンスの昇順配列を仮定する)に原問題を変換することである.だからk番目の小数の問題を解決すれば、元の問題も解決できる.
まず,配列AとBの要素個数がk/2より大きいと仮定し,Aのk/2番目の小さい要素とBのk/2番目の小さい要素をそれぞれ表すA[k/2-1]とB[k/2-1]の2つの要素を比較した.この2つの要素の比較には、>、
証明も簡単で、反証法を採用することができます.A[k/2-1]がマージ後のk番目の小さい値より大きいと仮定し、(k+1)番目の小さい値と仮定してもよい.A[k/2-1]はB[k/2-1]より小さいため、B[k/2-1]は少なくとも(k+2)番目の小さな値である.しかし、実際には、Aにおいて最大k/2-1個の元素がA[k/2-1]未満であり、Bにおいても最大k/2-1個の元素がA[k/2-1]未満であるため、A[k/2-1]未満の元素の個数は最大k/2+k/2-2であり、k未満であることは、A[k/2-1]が(k+1)番目の数であることと矛盾する.
A［k／2−1］＞B［k／2−1］では同様の結論が得られた.
A[k/2-1]=B[k/2-1]のとき,k番目の小さな数,すなわちこの等しい要素を見つけ,mと記す.AとBにはそれぞれk/2-1個の元素がm未満であるため、mはk番目に小さい数である.(ここで疑問に思う人もいるかもしれませんが、kが奇数であればmは中位数ではありません.ここでは理想化して考えていますが、実際のコードではやや異なり、まずk/2を求め、それからk-k/2を利用して別の数を得ることです.)
以上の解析により,再帰的にk番目の小さな数を探すことができる.さらに、いくつかの境界条件を考慮する必要があります. AまたはBが空の場合、B[k-1]またはA[k-1]に直接戻る. kが1の場合、A[0]およびB[0]の小さな値を返すだけです. A[k/2-1]=B[k/2-1]の場合、どちらかを返します.
コードは非常に簡潔で、効率も高いことがわかります.最良の場合、毎回kの半分の要素が削除されるので、アルゴリズム複雑度はlogkであり、中位数を求めるとkは(m+n)/2であるため、アルゴリズム複雑度はlog(m+n)である.
この文章は構想がはっきりしている.しかし、このC++コードはleetcodeで正常に動作しません.次に変更します.
がんばってください!
残念なことに、私は解決策を見つけただけです.集計法(鬼の集計ソートのような考え方で、以下に説明します)です.この方法の時間複雑度はO(m+n)ですが、時間複雑度のもっと簡単な方法があることに気づきました.二分検索のように、頭が大きくなっています.今はまだはっきりしていません.少しずつ来てください.
まず最も難しい方法を話しましょう:以下は私が抜粋したアルゴリズムの基本原理で、私が見た後も雲の中で霧の中で、私は何度も見てやっと理解して、この方法を考え出した人は本当にです.牛.
この解法の大まかな考え方は簡単で、A配列の中間要素とB配列の中間要素を比較して、小さい要素が存在する配列の前半と大きい要素が存在する配列の後半を削除することです.再帰する.
実は以上の解法を正しく実現するにはtrickyのほうがいいです.多くの境界状況にかかわる必要があるので、一つ一つ説明します.
最初のステップは、k番目の小さな要素findKthSortedArraysを探すことにテーマを変更する必要があります.(ここでkは1から計算)
なぜなら,medianに執着すると,要素の半分程度を削除して形成されたサブ問題では,依然としてmedianを探すことが保証されにくいからである.メディアの前または後を探すようになる可能性があります.
(この問題をよく考えればこの言葉が理解できる)
k番目の小要素に変更する利点は,削除した要素を考慮し,サブ問題でkの値を絶えず変更できることである.
(例えば、本来私たちが探しているメディアは5番目の数で、前の2つの数を削除すると、サブ問題では5-2=3番目の数を探すようになります)
A,B配列の総数のパリティを考慮するとfindKthSortedArraysを呼び出す問題に変換される.
第二部:findKthSortedArraysの実現
(一)まず,A配列がB配列より短いことを規定する.
このような処理の利点は,我々が必要とする(k−1)/2位置がある配列の全長よりも大きい可能性があり,Aが短いことを規定した後,Aを超える長さを考慮するだけで,状況を分けて議論する必要がないことである.
ここでは、なぜk/2ではないのかを考慮する必要があります.k/2±1?(k-1)/2
私の考えは次の通りです.
k=1,2の場合は、最初の2つの要素を比較する必要があるため、下に0と表示されます.
k=3,4の場合、1番目の要素を比較する必要があるため、下に1と表示されます.
まとめて得た.
(二)次に、特殊な状況を処理する.
(1)A配列が空の場合,B配列のk番目の要素を返す.
(2)k=1の場合、A[0]、B[0]の中のあの
(3)次に2つの状況に分けます.
(k-1)/2位置はA配列の長さを超えていますか?
(1)超えるとA配列の代表Acandiが最後の要素A[m-1]、Bの代表BcandiがB[k-m-1]となる
(a)Acandi==Bcandiであれば、ちょうどk-2個の要素がAcandi、Bcandiより小さいので、k番目の要素がAcandi/Bcandi
(b)Acandi>Bcandiでは、最大でm-1+k-m-1=k-2個の要素だけがBcandiよりも小さいので、Bcandiを含む以前のk-m個のB配列要素はk番目の数ではないに違いないので、削除すると、サブ問題はk-(k-m)番目の要素を探すことになる
(c)Acandi
(a)Acandi==Bcandiで、(k-1)/2+(k-1)/2=k-1の要素がAcandi、Bcandiより小さいので、k番目の要素がAcandi/Bcandi
等しくなければ,Acandi,Bcandi自身が取捨選択する必要があるかどうかについては分析に注意する.
いくつかの例を挙げて簡単に分析すると,kが奇数の場合,小さなcandidateを残し,大きなものを捨てる必要があることが容易に分かった.
kが偶数の場合、大きなcandidateを残し、小さいものを捨てる必要があります.
(b)Acandi > Bcandi
(b.1)kは奇数であり、Bcandiを保持し、Bcandiの前の(k-1)/2個の要素を削除し、AおよびAの後ろの要素(Aの前(k-1)/2個の要素を保持する)を削除する
(b.2)kは偶数で、Acandiを保持し、Bcandiおよび前の(k-1)/2+1個の要素を削除し、A後の要素(A中の前(k-1)/2+1個の要素を保持する)を削除する
(c)Acandi < Bcandi
ハハ~上も頭が痛いかもしれませんね~後で私はこの問題をもっとはっきり説明できる文章を見つけました:
中心思想は:この2つの配列nums 1とnums 2はそれぞれ2つの部分に分かれている.
nums 1[0......pa-1]およびnums 1[pa......s 1-1](nums 1長s 1)nums 2[0......pb-1]およびnums 2[pb......s 2-1](nums 2長s 2)
ここでpa+pb=kは,アルゴリズム導論においてpa=pb=k/2で議論される(そこではまず1つの配列を2つの並べられた等しい長さの配列に分けるためである)が,ここで実際にコードを書く際には配列長がk/2を超えない場合,を考慮する必要がある.
最後にmedianof two sorted arraysから非常に良い方法を見た.原文は英語で説明されていますが、ここでは中国語に翻訳します.この方法の核心は,中位数が実際には(m+n)/2番目の小さい数であるように,k番目の小数点を探す問題(2つの元のシーケンスの昇順配列を仮定する)に原問題を変換することである.だからk番目の小数の問題を解決すれば、元の問題も解決できる.
まず,配列AとBの要素個数がk/2より大きいと仮定し,Aのk/2番目の小さい要素とBのk/2番目の小さい要素をそれぞれ表すA[k/2-1]とB[k/2-1]の2つの要素を比較した.この2つの要素の比較には、>、
証明も簡単で、反証法を採用することができます.A[k/2-1]がマージ後のk番目の小さい値より大きいと仮定し、(k+1)番目の小さい値と仮定してもよい.A[k/2-1]はB[k/2-1]より小さいため、B[k/2-1]は少なくとも(k+2)番目の小さな値である.しかし、実際には、Aにおいて最大k/2-1個の元素がA[k/2-1]未満であり、Bにおいても最大k/2-1個の元素がA[k/2-1]未満であるため、A[k/2-1]未満の元素の個数は最大k/2+k/2-2であり、k未満であることは、A[k/2-1]が(k+1)番目の数であることと矛盾する.
A［k／2−1］＞B［k／2−1］では同様の結論が得られた.
A[k/2-1]=B[k/2-1]のとき,k番目の小さな数,すなわちこの等しい要素を見つけ,mと記す.AとBにはそれぞれk/2-1個の元素がm未満であるため、mはk番目に小さい数である.(ここで疑問に思う人もいるかもしれませんが、kが奇数であればmは中位数ではありません.ここでは理想化して考えていますが、実際のコードではやや異なり、まずk/2を求め、それからk-k/2を利用して別の数を得ることです.)
以上の解析により,再帰的にk番目の小さな数を探すことができる.さらに、いくつかの境界条件を考慮する必要があります.
double findKth(int a[], int m, int b[], int n, int k)
{
//always assume that m is equal or smaller than n
if (m > n)
return findKth(b, n, a, m, k);
if (m == 0)
return b[k - 1];
if (k == 1)
return min(a[0], b[0]);
//divide k into two parts
int pa = min(k / 2, m), pb = k - pa;
if (a[pa - 1] < b[pb - 1])
return findKth(a + pa, m - pa, b, n, k - pa);
else if (a[pa - 1] > b[pb - 1])
return findKth(a, m, b + pb, n - pb, k - pb);
else
return a[pa - 1];
}
class Solution
{
public:
double findMedianSortedArrays(int A[], int m, int B[], int n)
{
int total = m + n;
if (total & 0x1)
return findKth(A, m, B, n, total / 2 + 1);
else
return (findKth(A, m, B, n, total / 2)
+ findKth(A, m, B, n, total / 2 + 1)) / 2;
}
};
コードは非常に簡潔で、効率も高いことがわかります.最良の場合、毎回kの半分の要素が削除されるので、アルゴリズム複雑度はlogkであり、中位数を求めるとkは(m+n)/2であるため、アルゴリズム複雑度はlog(m+n)である.
この文章は構想がはっきりしている.しかし、このC++コードはleetcodeで正常に動作しません.次に変更します.
class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int m = nums1.size(), n = nums2.size();
int total = m+n;
if(total%2 == 1)
return helper(nums1, m, nums2, n, total/2+1, 0, 0);
else
return (helper(nums1, m, nums2, n, total/2, 0, 0) + helper(nums1, m, nums2, n, total/2+1, 0, 0))/2;
}
double helper(vector& nums1, int m, vector& nums2, int n, int k, int start1, int start2){
if(m > n)
return helper(nums2, n, nums1, m, k, start2, start1);
if(m == 0)
return nums2[k-1];
if(k == 1)
return min(nums1[start1], nums2[start2]);
int a = min(k/2, m); // k/2 nums1
int b = k-a;
if(nums1[a+start1-1] <= nums2[b+start2-1]){
return helper(nums1, m-a, nums2, n, k-a, start1+a, start2);
}
else{
return helper(nums1, m, nums2, n-b, k-b, start1, start2+b);
}
}
}; がんばってください!