您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

HDU 1004 最受歡迎氣球顏色：字符串計數 C 語言解法

編輯：關於C語言

HDU 1004 最受歡迎氣球顏色：字符串計數 C 語言解法

HDU 1004 題目要求統計多組測試數據中出現次數最多的氣球顏色字符串。本文提供基於二維字符數組 + 計數數組的直觀 O(n²) 解法，並分析優化方向（哈希表/Trie 樹），適合 ACM 入門練習。

題目大意

多組測試數據，每組先讀整數 N (0 < N ≤ 1000)。
隨後 N 行，每行一個顏色字符串（≤15 個小寫字母）。
N=0 結束輸入。
輸出每組出現次數最多的顏色（保證唯一）。

算法思路：暴力計數

用 `char color[1000][16]` 存儲所有顏色字符串。
用 `int cnt[1000]` 記錄每個顏色出現次數，初始化為 0。
雙重循環：外層 `i=0..N-1`，內層 `j=i+1..N-1`，若 `strcmp(color[i], color[j])==0` 則 `cnt[i]++`。
遍歷 `cnt` 找最大值對應下標 `max_idx`，輸出 `color[max_idx]`。

完整 C 語言代碼

#include <stdio.h>
#include <string.h>

int main() {
    int n;
    char color[1000][16]; // 15字符 + \0
    int cnt[1000];

    while (scanf("%d", &n) == 1 && n) {
        // 讀入並初始化計數
        for (int i = 0; i < n; i++) {
            scanf("%15s", color[i]); // 限制寬度防溢出
            cnt[i] = 0;
        }

        // 兩兩比較計數
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (strcmp(color[i], color[j]) == 0) {
                    cnt[i]++;
                }
            }
        }

        // 找最大計數對應的顏色
        int max_idx = 0;
        for (int i = 1; i < n; i++) {
            if (cnt[i] > cnt[max_idx]) max_idx = i;
        }
        printf("%s\n", color[max_idx]);
    }
    return 0;
}

複雜度分析

時間：O(N² × L)，N≤1000，L≤15，最約 1.5×10⁷ 次字符比較，1 秒內輕鬆通過。
空間：O(N × L) ≈ 16KB，極小。

優化方向（進階）

方法	時間複雜度	實現要點
哈希表	O(N × L) 平均	自定義字符串哈希（如 DJB2），處理衝突（鏈表/開放定址）
Trie 字典樹	O(N × L)	每個節點 26 個子指針 + 計數器，適合大量字符串前綴查詢
排序後計數	O(N log N × L)	`qsort` + `strcmp` 排序，相同字符串相鄰，單次遍歷計數
C++ STL `unordered_map`	O(N × L) 平均	`unordered_map` 一行代碼搞定

排序計數法 C 實現（推薦平衡）

int cmp_str(const void *a, const void *b) {
    return strcmp((const char*)a, (const char*)b);
}

// 在 while 循環內：
qsort(color, n, 16, cmp_str); // 排序

int max_cnt = 1, cur_cnt = 1;
char *max_color = color[0];
for (int i = 1; i < n; i++) {
    if (strcmp(color[i], color[i-1]) == 0) {
        cur_cnt++;
    } else {
        cur_cnt = 1;
    }
    if (cur_cnt > max_cnt) {
        max_cnt = cur_cnt;
        max_color = color[i];
    }
}
printf("%s\n", max_color);