C語言查找首個唯一字符：雙重循環法 vs 哈希表法對比

C語言查找首個唯一字符：雙重循環法 vs 哈希表法對比

同一問題的兩種實現：小數據量適合的雙重循環 O(n²)，大數據量必須的哈希表法 O(n)。

方法一：雙重循環 (適合短字符串)

int find_bruteforce(char *s, int len) {
    int freq[20] = {0};  // 假設長度≤20
    for (int i = 0; i < len; i++) {
        int c = 0;
        for (int j = 0; j < len; j++)
            if (s[i] == s[j]) c++;
        freq[i] = c;
    }
    for (int i = 0; i < len; i++)
        if (freq[i] == 1) return i;
    return -1;
}

時間 O(n²)，空間 O(n)。n≤100 可接受。

方法二：哈希表/計數數組 (標準解，適合長字符串)

#define TABLE_SIZE 256

char first_unique_hash(char *s) {
    int hash[TABLE_SIZE] = {0};
    char *p = s;
    while (*p) hash[(unsigned char)*p++]++;
    p = s;
    while (*p) {
        if (hash[(unsigned char)*p] == 1) return *p;
        p++;
    }
    return 0;
}

int main() {
    char s[1000];
    gets(s);  // 注意：gets 不安全，教學用
    char c = first_unique_hash(s);
    if (c) printf("首個唯一：%c\n", c);
    else printf("無唯一字符\n");
    return 0;
}

對比總結

面試建議

• 先說雙重循環思路，再優化到哈希表
• 強調 unsigned char 防負索引
• 討論 Unicode 情況下用 unordered_map/哈希表
• 可延伸：流式數據、滑動窗口、Top K 唯一字符