algorithm – 使用分而治之的两个大小为n的数据库中的第n个最小
我们有两个大小为n的数据库包含没有重复的数字.所以,我们总共有2n个元素.可以通过一次查询到一个数据库来访问它们.查询是这样的,你给它一个k,它返回该数据库中的第k个最小的条目.我们需要在O(logn)查询中的所有2n个元素中找到第n个最小的条目.我的想法是使用分而治之,但我需要一些帮助来思考这个问题.谢谢！
解决方法以下是我的想法.由于这是一个教育问题,我建议你停止阅读,如果任何一点让你思考,“啊哈,我没有想到这一点,我可以自己进一步思考这些问题”.1)与sdcwc相同的观察结果：对于它是从0还是1开始可能有轻微的狡辩,数据库可以被认为是一个排序的数组.我要求元素0,我得到最小的.我要求12,我得到第13个最小的.等等.我发现这更容易想象. 2)我们知道我们正在寻找一种O(log n)算法.这意味着粗略地说我们正在寻找两件事之一： >要么我们从计算最小元素开始,然后计算第二个最小,第四个最小,第8个等,直到我们达到我们想要的大小,每个步骤都在恒定时间内.这对我来说听起来并不乐观. 实际上每次不一定必须是n / 2.它可以是n / 3,或999 * n / 1000,结果仍然是O(log n).但是首先寻找n / 2并没有什么坏处. 3)我们如何减少这样的问题？好吧,如果我们可以从一个数组的开头打折/删除m个元素,或者小于第k个最小的m元素,那么我们可以找到所得到的数组对中的(km)最小元素,它将是第k个最小的原始数组. 4)最后,突破性观察是,如果阵列A的第m个最小元素小于阵列B的第m个最小元素,那么A的第m个元素不可能是两个阵列组合的第(2m)个最小元素.它小于那个(或相同的值：我不确定“没有重复”是否意味着“每个数据库中没有重复”,或“数据库之间没有重复”),因为最多只有2 *(m- 1)严格小于两个阵列组合的元素. 除非我犯了错误,否则剩下的就是编码.当k为奇数时,利用一个小的额外参数来解释1的off-by,该解决方案实际上是O(log k),其是O(log n),因为k <= 2 * n. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |