C語言實作：已排序陣列中找出出現次數最多的元素頻率

有序陣列眾數頻率統計

給定一個已由小到大排序的整數陣列，找出其中出現次數最多的元素其出現次數（即眾數頻率）。利用有序特性可在 O(n) 時間單次遍歷完成。

問題描述

陣列 {1, 2, 2, 3, 3, 3, 4, 5, 5, 6} 已排序。3 出現 3 次為最多，故答案為 3。

原程式碼邏輯分析

原始碼採用兩階段：
1. 先建立不重複元素陣列 num[]。
2. 再對每個不重複元素，掃描原陣列計數並追蹤最大值。
時間複雜度 O(n²)，空間 O(n)。雖能得正解但非最佳。

最佳化單次遍歷法

因陣列已排序，相同元素相鄰。只需一次遍歷：

int max_freq = 1, curr_freq = 1;
for(i = 1; i < n; i++) {
    if(arr[i] == arr[i-1]) curr_freq++;
    else curr_freq = 1;
    if(curr_freq > max_freq) max_freq = curr_freq;
}

時間 O(n)，空間 O(1)。

完整程式碼（最佳化版）

#include <stdio.h>

int main()
{
    int arr[] = {1, 2, 2, 3, 3, 3, 4, 5, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int max_freq = 1, curr_freq = 1;
    int i;

    for(i = 1; i < n; i++)
    {
        if(arr[i] == arr[i-1]) curr_freq++;
        else curr_freq = 1;

        if(curr_freq > max_freq) max_freq = curr_freq;
    }

    printf("該陣列中重複次數最多為%d次\n", max_freq);
    return 0;
}

原始碼保留（教學參考）

/* 原始雙重迴圈版本 */
#include <stdio.h>

int main()
{
    int i, k, max = 0, j = 0, count = 0;
    int re_num[] = {1, 2, 2, 3, 3, 3, 4, 5, 5, 6};
    int num[10];

    num[0] = re_num[0];
    for(i = 0; i < 10; i++)
    {
        if(num[j] != re_num[i]) num[++j] = re_num[i];
    }

    for(i = 0; i < j; i++)
    {
        count = 0;
        for(k = 0; k < 10; k++)
        {
            if(num[i] == re_num[k]) count++;
            if(max < count) max = count;
        }
    }
    printf("該陣列中重複次數最多為%d次\n", max);
    return 0;
}

延伸應用

• 若需同時輸出眾數值，可在更新 max_freq 時記錄對應元素。
• 若陣列未排序，可先排序 O(n log n) 或用雜湊表 O(n) 空間換時間。