求 Max 和 4th Max 元素
Find the Max and 4th Max element
求一个数组的最大值和第 4 个最大值,最少需要多少次比较?我假设我必须使用类似于 MinMax 的算法以及在此处找到的解决方案:
Find the 2nd largest element in an array with minimum number of comparisons\
但我不确定我将如何使比赛风格适应这种情况。
有趣的问题...
我认为诀窍只是 运行 第二次参加比赛,但将最大和第二大的比赛从比赛中移除(由比赛 #1 确定)。
锦标赛 #1:在 (1) [最大] 和 (2) [第二大] 中找到
第 2 场比赛:(1) 和 (2) 从比赛中移除。在 (3) [最大] 和 (4) [第二大] 中查找。这些将是原始集合中的第三大和第四大(分别)。
- n - 1
- log n - 1
- (n-2) - 1
- log (n-2) - 1
[编辑]:为了完整性,我最好尝试一些数学运算。
(1) + (2) + (3) + (4)
=> (n - 1) + (log n - 1) + ((n - 2) - 1) + (log (n-2) - 1)
=> 2n + (log n) + (log (n-2)) - 6
=> 2n + log (n^2 - 2n) - 6
求一个数组的最大值和第 4 个最大值,最少需要多少次比较?我假设我必须使用类似于 MinMax 的算法以及在此处找到的解决方案:
Find the 2nd largest element in an array with minimum number of comparisons\
但我不确定我将如何使比赛风格适应这种情况。
有趣的问题...
我认为诀窍只是 运行 第二次参加比赛,但将最大和第二大的比赛从比赛中移除(由比赛 #1 确定)。
锦标赛 #1:在 (1) [最大] 和 (2) [第二大] 中找到
第 2 场比赛:(1) 和 (2) 从比赛中移除。在 (3) [最大] 和 (4) [第二大] 中查找。这些将是原始集合中的第三大和第四大(分别)。
- n - 1
- log n - 1
- (n-2) - 1
- log (n-2) - 1
[编辑]:为了完整性,我最好尝试一些数学运算。
(1) + (2) + (3) + (4)
=> (n - 1) + (log n - 1) + ((n - 2) - 1) + (log (n-2) - 1)
=> 2n + (log n) + (log (n-2)) - 6
=> 2n + log (n^2 - 2n) - 6