我想解决这个问题..
给定n个数字列表,我们希望从列表中找到最小和最小的数字.描述一种分而治之的算法来解决这个问题.假设对于整数k,n = 2 ^ k.使用算法的比较次数不应超过3n/2 - 2,即使在最坏的情况下也是如此.
我目前的解决方案是使用选择算法来获得中位数,然后将列表分成L1(包含小于或等于中位数的元素),R(中位数),L2(包含比中位数更大的所有元素).这是对的吗？如果是这样,接下来该怎么办？
请注意,中值选择算法使用Θ(n)比较,但这并不意味着它最多使用3n/2 - 2比较.事实上,我认为它使用了更多,这可能会排除您的解决方案策略.
作为提示:将此问题视为为所有2 k建立淘汰赛; 每轮的获胜者(两个数字中较小的一个)前进到下一轮.需要多少次比较才能实现？接下来,请注意第二小数字必须"丢失"到最小数字.第二小数字也是"丢失"到最小数字的最小数字.鉴于此,您能否有效地找到第二小的数字？
希望这可以帮助!