这就是我的想法。由于这是一个教育问题，因此我建议您停止阅读，如果有任何观点使您认为“啊哈，我没想到，我可以自己进一步考虑”。

1）与sdcwc相同的观察结果：对于是否以0或1开头可能会有一点细微的争议，可以将数据库视为排序数组。我要求元素0，我得到最小的元素。我要求12，我得到第13位。等等。我发现这更容易可视化。

2）我们知道我们正在寻找O（log n）算法。大致而言，这意味着我们正在寻找以下两项之一：

• 我们要么从计算最小的元素开始，然后计算第二个最小，第四个最小，第8个，依此类推，直到达到所需的大小，并且每一步都是固定的时间。这对我来说听起来并不乐观。

• 或者我们从大小为n的问题开始，然后执行一些恒定时间操作，这使我们能够通过解决大小为n / 2的问题来解决原始问题。显然，我们可以在恒定时间内解决n = 1的问题，从而完成算法。这听起来似乎更合理。

实际上，不必每次都为n / 2。可能是n / 3或999 * n / 1000，结果仍然是O（log n）。但是先寻找n / 2是没有害处的。

3）我们如何减少这样的问题？好吧，如果我们可以从一个数组或另一个数组的开始处减去/删除m个元素，使其小于第k个最小元素，那么我们可以找到结果对数组中第（km）个最小元素，它将是原始数组的第k个最小数组。

4）最后，突破性观察是，如果数组A的第m个最小元素小于数组B的第m个最小元素，那么A的第m个元素就不可能成为两个数组的第（2m）个最小元素。它小于该值（或相等值：我不确定“不重复”是指“每个数据库中不重复”还是“两个数据库之间不重复”），因为最多有2
*（m- 1）严格小于两个数组组合的元素。

除非我犯了一个错误，否则其余的都是编码。当k为奇数时，用一个小的额外参数来说明偏离1的情况，该解决方案实际上是O（log k），因为k <= 2 * n，所以它是O（log n）。