算法:从未知数组中查找第二个最小元素的索引

Question

我一直在思考我的家庭作业问题.我欢迎(并且更喜欢)有关如何解决此问题的任何建议或方法.

基本上,我有一个大小为N的数组A.我们不知道这些元素,但我们知道它们是截然不同的.我唯一拥有的是一个将在N中取两个指数(i,j)的人.然后这个人会告诉我A [j]是<或> A [i].我想通过向这个人询问<= n + log n个问题找到找到第二个最小元素索引的算法.

Answer 1

这个答案描述了如何找到第二大元素; 找到第二小的可以类似地完成.为简单起见,我们还假设所有数字都不同.

为了找到最大的元素,让我们建立一个'锦标赛'树:配对元素,决定哪个更大(一个是'赢家')然后配对获胜者,决定哪个更大,等等,直到你找到'冠军',这是最大的元素.这需要n步.现在,必须将第二大元素与冠军进行比较.(因为只有冠军才能击败它).log n元素已经与冠军相提并论,所以从这些中挑选出最大的; 这需要log n步骤.

作为一个例子,让我们看看它如何适用于数字元组[6,4,3,5,2,1].在第一轮中,对是(6,4),(3,5),(2,1).获胜者是每对中更大的元素,即6,5,2.在第二轮中,对是(6,5),2.(2在这里没有对,因此它会自动升级到下一轮).第二轮的获胜者是6和2,在第三轮中唯一的一对是(6,2),6是获胜者.现在,通过配对元素并选择胜利者,我们构建了一个(根,二进制)树:

这个树具有对于我们拥有的节点x及其子节点的属性,因此我们知道最大元素是顶部(在根节点)的元素.我们也知道第二个最伟大的元素没有达到顶峰,因此它在树中有一个父元素.但它的父亲大于或等于,所以在树的某个层面上,最大元素的子女之一就是.(换句话说,第二大元素只能被最大元素'击败'.因此,我们所要做的就是回到最大元素所采取的路径并收集所有直接的孩子,我们知道其中第二大孩子.在我们的例子中,这些是元素2,5,4.(一般来说,有关于它们的地方y,zx>=y, x>=zwwwlog nlog表示基数为2的对数,因为树log n高约.).从这些元素我们选择最大的任何方法采取log n步骤,我们发现第二大.

所有这些都可能让我们想起一个总冠军,其中数字表示每个球队的"好"程度,因此称为"冠军树".