C 语言第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 大元素。

完整程序

#include <stdio.h>

int main(void)
{
    int n, a[500];
    if (scanf("%d", &n) != 1 || n < 2 || n > 500) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    // 初始化第一大 (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];
        }
    }

    printf("%d\n", second);
    return 0;
}

运行示例

输入：

5
3 9 1 7 5

输出：

7