0

この質問は何度も聞かれたと思いますが、まだ明確な解決策はありません! とにかく、これは私が O(k) (おそらく O(logm + logn) も) で良い答えとして見つけたものです。しかし、M_B > M_A (またはその他の方法) の場合、M_B の後の要素を破棄する必要がある部分がわかりません。しかし、ここではその逆です - M_B の前にある要素をスローします。誰でも理由を説明できますか？

http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-s01/recitations/rec03/rec03.ps

もう 1 つの質問は、K/2 を実行することです...実行する必要がありますが、私には明らかではありません。

[編集1]

Example
A = [2, 9, 15, 22, 24, 25, 26, 30]
B = [1, 4, 5, 7, 18, 22, 27, 33]
k= 6

Answer is 9 (A[1])

O(Log k) で解決したい場合は、毎回 k/2 要素をスローする必要があると思います。基本的な解決策: K < 2 の場合: A[0]、A[1]、B[0]、B[1] から 2 番目に小さい要素を返します。そうでない場合: A[k/2] と B[k/2] を比較します。 A[k/2] < B[k/2] の場合: k 番目に小さい要素は A[1 ... n] と B[1 ... K/2] にあります ... OK ここで k/ を投げます2 (A[k/2] > B[k/2] についても同様のことができます。次の質問は、k インデックスは K または k/2 ですか?

私がしていることは正しいですか？

4

1 に答える 1

2

そのアルゴリズムは悪くありません。私の意見では、SO で通常参照されているアルゴリズムよりも優れています。これは、はるかに単純であるためです。ただし、1 つの大きな欠点があります。両方のベクトルに少なくともk要素が必要です。(問題は、両方とも同じ数の要素 を持っていることを示してnいますが、それを指定することn ≥ kはありません。この関数では、ベクトルの大きさを伝えることさえできません。ただし、これは簡単に解決できます。演習として残します。一般に、さまざまなサイズの配列で機能するには、このようなアルゴリズムが必要ですが、実際にそうです; 前提条件を明確にする必要があるだけです.)

floorandの使用ceilは適切で具体的ですが、混乱を招く可能性があります。これを最も一般的な方法で見てみましょう。また、引用された解決策は、配列が 1-index であると仮定しているようです (つまりA[1]、最初の要素であり、ではありませんA[0])。ただし、これから書く説明では、より C に似た疑似コードを使用しているため、それがA[0]最初の要素であると想定しています。kしたがって、要素である結合セット内の要素を見つけるように記述します。最後に、これから説明するソリューションは、提示されたソリューションとは微妙に異なります。これは、最終的な状態で明らかになります。私見、それは少し良いです。(k+1)th

OK、がシーケンス内のx要素である場合、シーケンス内に より小さい要素kが正確に存在します。(繰り返し要素がある場合は扱いませんが、大きな違いはありません。注 3 を参照してください。)kx

それを知っていてA、Bそれぞれに要素があるとしますk。(これは、それぞれに少なくともk + 1要素があることを意味します。)よりも小さい負でない整数をk選択します。と呼びますi。そして、そうしましょjうk - i - 1（そのようにi + j == k - 1）。[以下の注 1 を参照してください。] 次に、要素A[i]と を見てくださいB[j]。A[i]他のケースではすべての名前を変更する必要があるだけなので、小さいとしましょう。すべての要素が異なると仮定していることを思い出してください。したがって、現時点でわかっていることは次のとおりです。

1）あるi要素がAあります< A[i]

2）あるj要素がBあります< B[j]

3)A[i] < B[j]

4) (2) と (3) から、次のことがわかります。

j5) である要素はせいぜいBある< A[i]

6) (1) と (5) から、次のことがわかります。

i + j7)要素はせいぜい一緒にAあるB< A[i]

8) しかしi + jはk - 1であるため、実際には次のことがわかっています。

9)kマージされた配列の要素は、より大きくなければなりませんA[i](A[i]最大でも要素 であるためi + j)。

答えが よりも大きくなければならないことがわかっているのでA[i]、A[0] から A[i] を破棄できます (実際には、配列ポインターをインクリメントするだけですが、事実上それらを破棄します)。i + 1ただし、元の問題から要素を破棄しました。したがって、要素の新しいセット (短縮されAたものとオリジナルのものB) から、 elementk - (i + 1)の代わりにelement が必要kです。

では、前提条件を確認してみましょう。Aと の両方が最初に要素要素をB持っていると言ったkので、両方とも少なくともk + 1要素を持っています。A新しい問題では、短縮されたものと元のものBがそれぞれ少なくともk - i要素を持っているかどうかを知りたいです。は大きくないBため、明らかにそうです。また、から要素を削除しました。元々は少なくとも要素を持っていたので、現在は少なくとも要素を持っています。それで大丈夫です。k - iki + 1Ak + 1k - i

最後に、終了条件を確認しましょう。最初に、非負の整数を選択すると言いiましjたi + j == k - 1。の場合は不可能ですk == 0が、の場合は可能ですk == 1。したがって、何か特別なkことをする必要があるのは、0 に達したときだけです。その場合、必要なことは returnmin(A[0], B[0])です。[これは、あなたが見たアルゴリズムよりもはるかに単純な終了条件です。注 2 を参照してください。]

では、ピッキングの良い戦略は何iですか? i + 1いずれかまたは要素を問題から削除することk - iになりますが、要素の半分にできるだけ近づけたいと考えています。したがって、 を選択する必要がありますi = floor((k - 1) / 2)。すぐにはわからないかもしれませんが、j = floor(k / 2).

AとのB要素が少ないケースを解決する部分は省略しています。複雑ではありません。ご自身で考えてみることをお勧めします。

[1] 見ていたアルゴリズムはi + j == k(偶数の場合) を選択し、または要素のkいずれかをドロップします。私の選択は（常に）それらの1つを小さくする可能性がありますが、その後ドロップまたは要素になります。したがって、それはわずかに速く収束するはずです。iji + j == k - 1i + 1j + 1

i + j == k[2] (彼らの) 選択と(私の)選択の違いi + j == k - 1は、終了条件で明らかです。これらの定式化では、 と の両方が正iでjなければなりません。どちらかが 0 の場合、0 の要素を削除するリスクがあり、無限再帰ループになるからです。したがって、定式化では、 の可能な最小値kは 1 ではなく 2 であるため、終了ケースは を処理k == 1する必要があり、2 つではなく 4 つの要素を比較する必要があります。価値があるのは、「2つのソートされたベクトルから2番目に小さい要素を見つける」の最良の解決策は次のとおりだと思います: min(max(A[0], B[0]), min(A[1], B[1 ]))、これには 3 つの比較が必要です。これによりアルゴリズムが遅くなることはありません。より複雑です。

[3] 要素が繰り返される可能性があるとします。実際、これは何も変わりません。アルゴリズムは引き続き機能します。なんで？のすべての要素Aが実際には実際の値と実際のインデックスのペアであり、同様に のすべての要素でBあると見なすことができ、ベクトル内の値を比較するときにインデックスをタイ ブレーカーとして使用することができます。Aベクトル間では、 ifのすべての要素を優先しA[i] ≤ B[j]ます。それ以外の場合は、 内のすべての要素にB。これは、実際には実際のコードをまったく変更しません。なぜなら、実際に異なる方法で比較を行う必要がないからです。ただし、証明のすべての不等式が有効になります。

于 2012-12-21T05:21:16.277 に答える