Java第38题：求数组中第二大的数

题目

从标准输入读入 n 个互不相同的整数，查找并输出其中的第二大数。

输入格式：第一行输入整数个数 n（n ≥ 2）；第二行输入 n 个整数。

输出格式：输出一个整数表示第二大数，末尾换行。

数据范围与约定：2 ≤ n ≤ 1000。

思路与算法

1. 单次遍历维护前两名
设置两个变量 first 和 second。遍历每个元素 x：若 x > first，则原来的最大值降为第二大 second = first，并更新最大值 first = x；否则若 x > second，更新 second = x。

2. 复杂度
无需对整个数组执行 O(n log n) 的完全排序，单次 O(n) 扫描即可快速求出前 K 大元素。

完整程序

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // 初始化第一大 (first) 和第二大 (second)
        int first = a[0], second = a[1];
        if (second > first) {
            int t = first;
            first = second;
            second = t;
        }

        // 单次遍历维护前两名：
        // 若遇到更大的数，原最大值降级为次大值；若介于两者之间，仅更新次大值
        for (int i = 2; i < n; i++) {
            if (a[i] > first) {
                second = first;
                first = a[i];
            } else if (a[i] > second) {
                second = a[i];
            }
        }

        System.out.println(second);
    }
}

运行示例

输入：

5
3 9 1 7 5

输出：

7