使用从给定的列表中查找第二小的数目分而治之 [英] Finding the second smallest number from the given list using divide-and-conquer

问题描述

我试图解决这个问题。

给定n个号码的列表，我们想寻找最小和第二小   从列表中的号码。描述一个分而治之的算法来解决这个问题。假设N = 2 ^ k代表一个整数k。比较使用的算法的数量应   不大于3N / 2 - 2，即使在最坏的情况下

Given a list of n numbers, we would like to find the smallest and the second smallest numbers from the list. Describe a divide-and-conquer algorithm to solve this problem. Assume that n = 2^k for an integer k. The number of comparisons using your algorithm should not be more than 3n/2 − 2, even in the worst case.

我的当前解决方案是使用选择算法，得到中值，然后将列表分为L1（包含元素小于或等于中值）中，R（中位数），L 2（包含所有元素比位数磨碎）。对不对？如果是的话，我应该怎么办？

My current solution is to use select algorithm to get the median and then divide the list into L1( contains element less than or equal to the median), R ( median), L2 ( contains all the elements grater than median). Is it correct? If so, what should I do next?

推荐答案

请注意，该中值选择算法使用＆的Theta;（n）的比较，但是，这并不意味着它使用至多为3n / 2 - 2比较。事实上，我认为它使用了很多，这可能排除了您的解决方案的策略。

Note that the median-selection algorithm uses Θ(n) comparisons, but that doesn't mean that it uses at most 3n/2 - 2 comparisons. In fact, I think it uses a lot more, which probably rules out your solution strategy.

作为一个提示：觉得这个问题是建立一个淘汰赛的所有2 ^K ;每一轮（两个数中较小）的获胜者前进到下一个。需要多少的比较来实现呢？接下来，请注意，第二小的数字一定是失去，以最小的数字。所述第二小的数目也是最小数目丢失的最小数。鉴于此，你能有效地找到了第二小的数字？

As a hint: think of this problem as building an elimination tournament for all 2^k; the winner of each round (the smaller of the two numbers) advances to the next. How many comparisons are needed to implement that? Next, notice that the second-smallest number must have "lost" to the smallest number. The second-smallest number is also the smallest number that "lost" to the smallest number. Given this, could you efficiently find the second-smallest number?

希望这有助于！

这篇关于使用从给定的列表中查找第二小的数目分而治之的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！