C語言練習：單次掃描找出第二大整數（避開排序陷阱）

C語言練習：單次掃描找出第二大整數（避開排序陷阱）

問題：輸入一組整數（≤20 個，以 0 結束），包含正負數，至少 2 個數。輸出第二大值。注意：最大值可能重複，第二大值定義為嚴格小於最大值的最大值。

錯誤直覺

• 冒泡排序後取倒數第二個 → 失敗於最大值重複（如 5 5 3 排序後倒二仍為 5）。
• 找最大值後置為最小再找 → 失敗於最小值重複。

正確算法：單次遍歷維護兩大值

#include <stdio.h>
#include <limits.h>

int main() {
    int x, max1 = INT_MIN, max2 = INT_MIN;
    while (scanf("%d", &x) == 1 && x != 0) {
        if (x > max1) {
            max2 = max1;
            max1 = x;
        } else if (x > max2 && x < max1) {  // 關鍵：嚴格小於 max1
            max2 = x;
        }
    }
    printf("%d\n", max2);
    return 0;
}

樣例驗證

輸入：5 8 -12 7 0
過程：
  5 → max1=5, max2=MIN
  8 → max1=8, max2=5
 -12 → 無變化
  7 → max2=7 (7<8)
輸出：7  ✓

邊界情況測試

核心心得

• 第二大值始終伴隨最大值更新：新最大值產生時，舊最大值降為候選第二大。
• 條件 x > max2 && x < max1 精確排除等於最大值的情況。
• 單次掃描 O(n)、O(1) 空間，比排序 O(n log n) 更優。

此題考察對「第二大」定義的精確理解與變量維護技巧，是基礎算法面試必考點。