C語言找出字串中第一個不重複字元：雙掃描法與哈希表優化完整解析

問題描述

輸入字串，找出**第一個**只出現一次的字元。例：`"abaccdeff"` → `'b'`。

方法一：雙重迴圈暴力法（小字串適用）

char first_unique_brute(const char *s) {
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++)
            if (s[i] == s[j]) count++;
        if (count == 1) return s[i];
    }
    return '\0'; // 無唯一字元
}

時間 O(n²)，空間 O(1)。適合 n < 1000。

方法二：哈希表/計數陣列法（大字串最佳）

#include 

char first_unique_hash(const char *s) {
    if (!s) return '\0';
    int count[256] = {0}; // ASCII 256 字元

    // 第一次掃描：統計頻率
    for (const char *p = s; *p; p++)
        count[(unsigned char)*p]++;

    // 第二次掃描：找第一個 count==1
    for (const char *p = s; *p; p++)
        if (count[(unsigned char)*p] == 1)
            return *p;

    return '\0';
}

時間 O(n)，空間 O(1)（固定 256 `int`）。**標準解法**。

關鍵細節：`unsigned char` 索引

`char` 有無號之分，負值作索引會越界。**必須轉換**：`(unsigned char)*p` 或 `*p & 0xFF`。

完整測試程式

#include 
#include 

char first_unique(const char *s) { /* 方法二實作 */ }

int main() {
    char str[1000];
    printf("Enter string: ");
    fgets(str, sizeof(str), stdin);
    str[strcspn(str, "\n")] = '\0'; // 移除換行

    char c = first_unique(str);
    if (c) printf("First unique: '%c'\n", c);
    else puts("No unique character.");
    return 0;
}

進階變體

• Unicode/多位元組字元：改用雜湊表（`uthash` 或自定）以 `uint32_t` 為鍵。
• 串流資料：單次掃描，維護「候選佇列」+「計數表」，新字元入隊，重複字元標記移除。
• 回傳索引而非字元：第二次掃描回傳 `p - s`。

總結

第一個不重複字元 = **雙掃描 + 固定大小計數陣列**。第一掃建立頻率表，第二掃按原序尋找 `count==1`。核心技巧：`unsigned char` 索引避免負值越界。時間 O(n)，空間 O(1)，完美解決。