我正在研究关于在leetcode中找到两个排序数组的并集中的第k个最小元素的文章.我不认为算法是正确的.有这条线:我们观察到当Ai <Bj时,那么Ai <Bj-1必定是真的.另一方面,如果Bj <Ai,则Bj <Ai-1..怎么可能对任何i和j？
其次,这条线也让我困惑:我们试图通过比较A和B的中间元素来解决这个棘手的问题,我们将其识别为Ai和Bj.如果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作为细分索引来细分数组.但是怎么样？我们应该丢弃哪部分？艾和Bj本身怎么样？
我们观察到当Ai <Bj时,那么Ai <Bj-1必定是真的.另一方面,如果Bj <Ai,则Bj <Ai-1.为什么？
将其分解为子命题会产生以下解释(请记住,索引开始于0,但这A0是第一个最小的项,并且A1是第二个最小的项,依此类推):
i + j = k - 1 (根据定义,不变)Bj-1 < Ai < Bj.那Ai一定是k最小的.这是因为Ai大于中的i项目A并且大于中的j项目B.所以它比一共i + j = k - 1项目更重要.这意味着它在合并列表中的索引A|B将是k - 1,因此它将是该k列表中的第th项.Ai-1 < Bj < Ai.然后Bj必须是k最小的,通过2中的同一推理线.Bj-1 < Ai < Bj和(b)Ai-1 < Bj < Ai都是假的.那么很明显,如果Ai < Bj那时A1 < Bj-1,因为否则(a)将是真的.同样,如果Bj < Ai那时Bj < Ai-1,因为否则,(b)将是真实的.我告诉你,你想要解释这些陈述而不是整个算法.(但如果你愿意,我会说更多.)
还要注意,正如Daniel Fischer的回答提醒我的那样,只有没有重复的情况下,上述推理才有效; 称这个命题为0.