algorithm - 使用分治法从给定列表中找到第二小的数字

Question

我正在努力解决这个问题..

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.

我目前的解决方案是使用select算法获取中位数，然后将列表分为L1(包含小于或等于中位数的元素)，R(中位数)，L2(包含所有大于中位数的元素)。这是对的吗？如果是这样，我接下来应该做什么？

Answer 1

请注意，中值选择算法使用 Θ(n) 比较，但这并不意味着它最多使用 3n/2 - 2 次比较。事实上，我认为它使用的更多，这可能排除了您的解决方案策略。

提示:将这个问题想象成为所有 2^k 建立淘汰赛；每轮的获胜者(两个数字中较小的那个)进入下一轮。需要多少比较才能实现？接下来，请注意第二小的数字必须“输”给最小的数字。第二小数也是“输”给最小数的最小数。鉴于此，您能否有效地找到第二小的数字？

希望这对您有所帮助!