劍指 Offer：陣列中出現次數超過一半的數字（九度 OJ 1370）——排序取中位數法

題目

陣列長度 n ≤ 100,000，找出現次數 > n/2 的數，不存在輸出 -1。

解法 1：排序 + 取中位數 + 驗證（AC）

1. 快排 O(n log n)
2. 中位數 a[n/2] 必為候選答案（若存在過半數，排序後必佔據中間位置）
3. 線性掃描計數驗證，O(n)

void qsort(int l, int r) {
    if (l >= r) return;
    int pivot = arr[l], i=l, j=r;
    while (i=pivot) j--;
        swap(i,j);
        while (in/2 ? mid : -1);
    }
}

解法 2：哈希統計（大數據超時）

用結構體陣列記錄 (value, count)，查找用線性搜尋 O(n²)，n=100,000 且值不重複時 TLE。可改用雜湊表或 Boyer-Moore 投票算法 O(n) O(1) 空間。

AC 記錄

Time: 800 ms, Memory: 1304 KB (C, 九度 OJ 1370)