查找数组最大值和次最大值的算法

可以使用以下算法高效地找到数组 A[1..n] 中的最大值和次最大值:

  1. 初始化: 设置两个变量 maxsecond_max 为数组的前两个元素 A[1] 和 A[2]。如果 A[2] 大于 A[1],则交换它们的值。
  2. 遍历: 从数组的第三个元素 A[3] 开始遍历到最后一个元素 A[n]。
    • 对于每个元素 A[i],如果 A[i] 大于 max,则将 second_max 更新为 max,并将 max 更新为 A[i]。
    • 否则,如果 A[i] 大于 second_max 且小于 max,则将 second_max 更新为 A[i]。
  3. 返回: 返回 maxsecond_max

时间复杂度分析:

该算法需要遍历数组一次,并在每个元素上进行最多两次比较。因此,该算法的最坏情况时间复杂度为 O(n)

例子:

对于数组 A = [3, 1, 4, 2, 5], 该算法将返回 max = 5second_max = 4