在最多n + log 2(n)-2比较中找到数组中的第二大数字

Question

给出一个n个不同数字的未排序数组作为输入,其中n是2的幂.给出一个算法,该算法识别数组中第二大的数字,并且最多使用n + log 2(n)-2比较.

Answer 1

1. 首先比较奇数和偶数位置的n元素数组的元素,并确定每对元素的最大元素.此步骤需要n/2次比较.现在你只有n/2个元素.继续成对比较以获得n/4,n/8,...元素.找到最大元素时停止.该步骤总共需要n/2 + n/4 + n/8 + ... + 1 = n-1个比较.
2. 在前一步骤中,立即将最大元素与log 2(n)其他元素进行比较.您可以在log 2(n)-1比较中确定这些元素中最大的元素.那将是阵列中第二大的数字.

示例:8个数字的数组[10,9,5,4,11,100,120,110].

1级比较:[10,9] - > 10 [5,4] - > 5,[11,100] - > 100,[120,110] - > 120.

比较2级:[10,5] - > 10 [100,120] - > 120.

3级比较:[10,120] - > 120.

最大值为120.立即与:10(在3级),100(在2级),110(在1级)进行比较.

第2步应该找到最大值10,100和110.这是110.这是第二大元素.

Answer 2

sly s 的回答来自这篇论文，但是他没有解释算法，这意味着遇到这个问题的人必须阅读整篇论文，而且他的代码也不是很流畅。我将给出上述论文中算法的关键，完成复杂性分析，并提供一个 Scala 实现，因为这是我在处理这些问题时选择的语言。

基本上，我们做两遍：

1. 找到最大值，并跟踪与最大值进行比较的元素。
2. 在与最大值进行比较的元素中找到最大值；结果是第二大元素。

在上图中，12 是数组中最大的数，在第一轮中与 3、1、11 和 10 进行了比较。在第二遍中，我们找到 {3, 1, 11, 10} 中最大的一个，即 11，它是原始数组中的第二大数。

时间复杂度：

• 因此，必须查看所有元素，n - 1以便比较 pass 1。
• 由于我们每次将问题分成两半，因此最多有log?n递归调用，对于每个递归调用，比较序列最多增加一个；log?n因此，log?n - 1比较序列的大小最多为，因此是第 2 遍的比较。

• 比较总数 <= (n - 1) + (log?n - 1)=n + log?n - 2

  def secondLargest(xs: IndexedSeq[Int]): Int = {
      def max(lo: Int, hi: Int, ys: IndexedSeq[Int]): (Int, IndexedSeq[Int]) = {
        if (lo >= hi) {
          (ys(lo), IndexedSeq.empty[Int])
        } else {
          val mid = lo + (hi - lo) / 2
          val (x, a) = max(lo, mid, ys)
          val (y, b) = max(mid + 1, hi, ys)
  
          if (x > y) {
            (x, a :+ y)
          } else {
            (y, b :+ x)
          }
        }
      }
  
      val (_, comparisons) = max(0, xs.size - 1, xs)
      max(0, comparisons.size - 1, comparisons)._1
  }