正在给定为输入的n不同数字,其中n是2的幂给出一个算法标识阵列中的第二大数量的未分类的数组,以及使用最多n +log₂(正) - 2比较。
解决方案例如:8个数字阵列[10,9,5,4,11,100,120,110]
1的水平比较:10.9] - > 10 [5,4] - > 5,[11100] - > 100, [120,110] - > 120
2的水平比较:[10.5] - > 10 [100,120] - > 120
3级比较: [10120] - > 120
最大是120.有人立刻相比:10(3级),100(2级),110(1级)
。步骤2应该找的10,100最大的,和110这是110。这是第二大因素。
You are given as input an unsorted array of n distinct numbers, where n is a power of 2. Give an algorithm that identifies the second-largest number in the array, and that uses at most n+log₂(n)−2 comparisons.
解决方案
Example: array of 8 numbers [10,9,5,4,11,100,120,110].
Comparisons on level 1: [10,9] ->10 [5,4]-> 5, [11,100]->100 , [120,110]-->120.
Comparisons on level 2: [10,5] ->10 [100,120]->120.
Comparisons on level 3: [10,120]->120.
Maximum is 120. It was immediately compared with: 10 (on level 3), 100 (on level 2), 110 (on level 1).
Step 2 should find the maximum of 10, 100, and 110. Which is 110. That's the second largest element.
更多推荐
寻找第二大数字阵列最多n +log₂(N)
发布评论