查找数组最大值和次最大值的算法
可以使用以下算法高效地找到数组 A[1..n] 中的最大值和次最大值:
- 初始化: 设置两个变量
max
和second_max
为数组的前两个元素 A[1] 和 A[2]。如果 A[2] 大于 A[1],则交换它们的值。 - 遍历: 从数组的第三个元素 A[3] 开始遍历到最后一个元素 A[n]。
- 对于每个元素 A[i],如果 A[i] 大于
max
,则将second_max
更新为max
,并将max
更新为 A[i]。 - 否则,如果 A[i] 大于
second_max
且小于max
,则将second_max
更新为 A[i]。
- 对于每个元素 A[i],如果 A[i] 大于
- 返回: 返回
max
和second_max
。
时间复杂度分析:
该算法需要遍历数组一次,并在每个元素上进行最多两次比较。因此,该算法的最坏情况时间复杂度为 O(n)。
例子:
对于数组 A = [3, 1, 4, 2, 5], 该算法将返回 max = 5
和 second_max = 4
。