寻找第二大数字阵列最多n +log₂（N）-2比较 [英] Find Second largest number in array at most n+log₂(n)−2 comparisons

问题描述

正在给定为输入的n不同数字，其中n是2的幂给出一个算法标识阵列中的第二大数量的未分类的数组，以及使用最多n +log₂（正） - 2比较。

解决方案

1. 开始，在奇数和偶数位置比较n个元素数组的元素，并确定每对的最大元素。此步骤需要n / 2比较。现在你只拿到N ​​/ 2个元素。继续两两比较，以获得N / 4，N / 8，...元素。停车时，最大的元素被发现。此步骤需要总数为n / 2 + N / 4 + N / 8 + ... + 1 = n-1个比较。
2. 在previous一步，最大的元素立即与log₂（n）的其他元素进行比较。您可以确定最大的这些元素的log₂（N）-1的比较。这将是在阵列中第二大数目。

---

例如：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.

解决方案

1. Start with comparing elements of the n element array in odd and even positions and determining largest element of each pair. This step requires n/2 comparisons. Now you've got only n/2 elements. Continue pairwise comparisons to get n/4, n/8, ... elements. Stop when the largest element is found. This step requires a total of n/2 + n/4 + n/8 + ... + 1 = n-1 comparisons.
2. During previous step, the largest element was immediately compared with log₂(n) other elements. You can determine the largest of these elements in log₂(n)-1 comparisons. That would be the second-largest number in the array.

---

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）-2比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！