私は、 leetcodeで2つのソートされた配列の和集合でk番目に小さい要素を見つけることに関する記事を研究していました。アルゴリズムが正しいとは思いません。この行があります：Ai <Bjの場合、Ai<Bj-1であることが真でなければならないという観察を行います。一方、Bj <Aiの場合、Bj<Ai-1です。。どのようにそれはどのように真実であることができますiかj？
そして第二に、この行も私を困惑させます。私たちは、AiとBjとして識別されるAとBの中間要素を比較することによって、このトリッキーな問題にアプローチしようとします。AiがBjとBj-1の間にある場合、i + j + 1の最小要素が見つかりましたが、それは真実であることがわかります。誰かが理由を説明できますか？本当にアルゴを理解したいのですが、配列をマージしてやったのですが、ここO(N)の時間に比べるとO(log N)時間がかかります。
これらのステートメントを個別に解釈していますが、それらは相互に構築されています。これが（私が思うに）あなたが参照しているテキストです：
不変量i+j = k – 1を維持する場合、Bj-1 <Ai <Bjの場合、Aiはk番目に小さい必要があります。そうでない場合、Ai-1 <Bj <Aiの場合、Bjはk番目に小さい必要があります。 。上記の条件のいずれかが満たされれば、完了です。そうでない場合は、iとjをピボットインデックスとして使用して、配列を細分化します。しかし、どのように？どの部分を破棄する必要がありますか？AiとBj自体はどうですか？
Ai <Bjの場合、Ai<Bj-1であることが真実である必要があることを観察します。一方、Bj <Aiの場合、Bj<Ai-1です。なんで？
これをサブ命題に分解すると、次の解釈が得られます（インデックス作成はから始まるが0、これがA0最初の最小アイテムでありA1、2番目に小さいアイテムであることに注意してください）。
i + j = k - 1（不変、定義による）Bj-1 < Ai < Bj。次に、 th最小Aiでなければなりません。kこれは、がのアイテムよりも大きく、のアイテムよりAiも大きいためです。だから、それはアイテムの合計よりも大きいです。つまり、マージされたリストのインデックスは、になり、そのリストの3番目のアイテムになります。iAjBi + j = k - 1A|Bk - 1kAi-1 < Bj < Ai。次に、2の同じ推論の行で、th番目に小さいBj必要があります。kBj-1 < Ai < Bjと（b）のAi-1 < Bj < Ai両方が偽であると仮定します。そうでなければ（a）が真になるので、Ai < Bjそれなら、それは非常に明白になります。A1 < Bj-1同様に、もしそうBj < AiならBj < Ai-1、そうでなければ（b）が真になるからです。アルゴリズム全体ではなく、これらのステートメントの説明が必要だということをお伝えします。（でも、よろしければもっとお話しします。）
ダニエル・フィッシャーの答えが私に思い出させるように、上記の推論は重複がない場合にのみ当てはまることに注意してください。その命題を0と呼びます。
Ai < Bjの場合、それは真実でなければならないという観察を行いますAi < Bj-1。一方、の場合Bj < Ai、Bj < Ai-1..どのようにそれがanyiとに当てはまるのjでしょうか？
とのすべてのペアに当てはまるわけではありませiんj。この記事は特別な状況を考慮しています。
Aまず、との共通要素の形式であっても、重複はないと想定されBます。第二に、
Ai < Bj ==> Ai < Bj-1, resp. Bj < Ai ==> Bj < Ai-1
どちらも_
Bj-1 < Ai < Bj resp. Ai-1 < Bj < Ai
保持します。したがって、これらの構成を除外し、すぐAi < Bj ==> Ai <= Bj-1にBj < Ai ==> Bj <= Ai-1従うと、厳密な不等式は、重複が存在しないという仮定に従います。
AiとBjとして識別されるAとBの中間要素を比較することにより、このトリッキーな問題にアプローチしようとします。AiがBjとBj-1の間にある場合、i + j+1の最小要素が見つかりました
配列Bには、jよりも小さい要素がBjあり、配列には、よりも小さい要素Aがあります（インデックスは0から始まります）。したがって、の場合、両方の配列には、。よりも小さい要素が正確に含まれます。iAiBj-1 < Ai < Bjj + iAi
あまりない。
まだ状況を考えていi + j = k-1ます。と仮定しましょうAi <= Bj。
Ai = Bj？Ai < Bj？ケース1の場合、mのような最小のインデックスAm = Ai、およびnのような最小のインデックスとしBn = Bjます。次に、両方の配列に、m + n <= i + j = k-1厳密に。よりも小さい要素Aiと、少なくとも。(i+1) + (j+1) = (k+1)よりも大きくない要素がありAiます。したがって、k番目に小さい要素はに等しくなりAiます。
2.については、考慮すべき3つのケースBj-1 < Ai、a）、b）Bj-1 = Ai、c）がありBj-1 > Aiます。
a）の場合、以下のj要素がBありAi、それらはすべて厳密に小さく、（上記のように）厳密に小さいm <= i要素と不明な数がありますが、少なくとも要素は。に等しくなります。したがって、両方の配列には、厳密に。よりも小さい要素が正確に存在し、少なくとも要素は。よりも大きくないため、両方の配列のk番目に小さい要素は一緒になります。AAimi-m+1Aij + m <= j + i = k-1Aij + m + (i-m+1) = j+i+1 = kAiAi
b）の場合、同じ推論は、両方の配列のk番目に小さい要素が一緒に等しいことを示していAiます。
残りのケースではAi < Bj-1、物事はほとんど複雑になりません。配列Bには少なくとも、以下のj要素が含まれBj-1、配列Aには少なくともi+1厳密により小さい要素が含まれるBj-1ため、両方の配列のk番目に小さい要素は最大で。になりBj-1ます。ただし、より小さくすることはできませんAi（よりも小さい要素Bを多く含むため、両方の配列に含まれるのは最大でよりも小さい要素です）。j-1Aii + (j-1) = k-2Ai
したがって、下の部分をAi配列から破棄し、A上の部分をBj-1配列から破棄して、B重複することなく続行できます。
変更されたのは、いくつかの厳密な不等式を弱い不等式に置き換える必要があるということだけでした。
コード（スライスする代わりに開始インデックスと長さを渡した方が効率的ですが、スライスするとコードが短くなります）：
def kthsmallest(A, B, k):
if k < 1:
return None
a_len, b_len = len(A), len(B)
if a_len == 0:
return B[k-1] # let it die if B is too short, I don't care
if b_len == 0:
return A[k-1] # see above
# Handle edge case: if k == a_len + b_len, we would
# get an out-of-bounds index, since i + j <= a_len+b_len - 2
# for valid indices i and j
if a_len + b_len == k:
if A[-1] < B[-1]:
return B[-1]
else:
return A[-1]
# Find indices i and j approximately proportional to len(A)/len(B)
i = (a_len*(k-1)) // (a_len+b_len)
j = k-1-i
# Make sure the indices are valid, in unfortunate cases,
# j could be set to b_len by the above
if j >= b_len:
j = b_len-1
i = k-1-j
if A[i] <= B[j]:
if j == 0 or B[j-1] <= A[i]:
return A[i]
# A[i] < B[j-1] <= B[j]
return kthsmallest(A[i:], B[:j], k-i)
# B[j] < A[i], symmetrical to A[i] < B[j]
if i == 0 or A[i-1] <= B[j]:
return B[j]
# B[j] < A[i-1]
return kthsmallest(A[:i], B[j:], k-j)