我们观察到
Ai < Bj，什么时候一定是正确的Ai < Bj-1。另一方面，如果Bj < Ai，那么Bj <Ai-1..哪一个i和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立即进行操作，然后严格的不等式随后假设不存在重复项。
我们尝试通过比较A和B的中间元素来解决这个棘手的问题，我们将它们标识为Ai和Bj。如果Ai在Bj和Bj-1之间，我们刚刚发现i + j + 1最小元素
在array中
B，
j元素小于
Bj，在array中
A，
i元素小于
Ai（索引从0开始）。因此，如果
Bj-1 < Ai <Bj两个数组一起包含恰好
j + i小于的元素
Ai。
如果重复，会有什么变化？
不多。
我们仍然考虑这种情况
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.，我们有三种情况要考虑，a）
Bj-1 < Ai，b）
Bj-1 = Ai，c）
Bj-1 > Ai。
在情况a）中，我们的
j元素
B不大于
Ai，并且它们都严格小于，并且我们的
m <=i元素中
A的严格小于
Ai（
m如上所述）和未知数，但至少
i-m+1等于
Ai。因此
j + m <= j + i =k-1，两个数组中恰好有元素严格小于
Ai，并且至少
j + m + (i-m+1) = j+i+1 =k不大于
Ai，因此两个数组中第k个最小的元素等于
Ai。
在情况b）中，相同的推理表明两个数组的第k个最小元素在一起等于
Ai。
在其余的情况下，
Ai <Bj-1情况几乎不会变得复杂。数组
B至少
j包含不大于的元素
Bj-1，并且数组
A至少
i+1包含严格小于的元素
Bj-1，因此两个数组的第k个最小元素在一起最大为
Bj-1。但是它不能小于
Ai（（
B最多
j-1包含小于的元素
Ai，因此两个数组一起最多
i+ (j-1) = k-2包含小于的元素
Ai）。
所以我们仍然可以丢弃下面部分
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)
