问题来源于 pongba 邮件列表的一个帖子。
问题描述：如何在 O(n) 时间内找到一个整数数组中的第二大元素？
遍历一次找到第一，是比较容易的事情，第二呢？那么在遍历时同时保存第一和第二就成。那个帖子中 fumin.shen 和 legendsland 的回答都很有启发性，我的代码正是根据 fumin.shen 的提示写出来的，如下：
public class HelloWorld {
public static void main(String[] args) {
int[] a = { 3, 4, 5, 6, 7, 8, 8, 9, 9, 2, -1 };
System.out.println(HelloWorld.getSecond(a));
}
public static int getSecond(int... a) {
int first = a[0];
int second = a[1];
if (a[0] < a[1]) {
first = a[1];
second = a[0];
}
for (int i = 2; i < a.length - 1; i++) {
if (a[i] > first) {
second = first;
first = a[i];
} else if (a[i] < first && a[i] > second) {
second = a[i];
}
}
return second;
}
}
本文从旧站搬迁而来。