C++ 字符串首個不重複字符：O(n) 時間 O(1) 空間的最優解法

問題描述

給定字符串，找出第一個只出現一次的字符。例如 "1222345678234543" → '1'（索引 0）。

核心思路：計數 + 索引記錄

利用固定大小數組（ASCII 256 或 128）記錄每個字符的：
1. 首次出現索引
2. 出現次數

單次遍歷構建統計表

struct Info { int idx = -1; int cnt = 0; };
Info stat[256]; // 覆蓋擴展 ASCII

for (int i = 0; i < len; ++i) {
    unsigned char c = str[i];
    if (stat[c].idx == -1) stat[c].idx = i; // 僅記錄首次
    stat[c].cnt++;
}

掃描統計表找最小索引

int ansIdx = INT_MAX;
for (int i = 0; i < 256; ++i)
    if (stat[i].cnt == 1)
        ansIdx = min(ansIdx, stat[i].idx);

char ans = (ansIdx == INT_MAX) ? '\0' : str[ansIdx];

複雜度分析

• 時間：O(n + Σ)，Σ=256 為字符集大小，視為常數 → O(n)。
• 空間：O(Σ) → O(1) 額外空間。

變體與擴展

• 僅小寫字母：數組縮為 26，c - 'a' 映射。
• Unicode 字符串：改用 unordered_map，空間變為 O(k)（k 為不同字符數）。
• 流式輸入：需兩遍掃描或雙端隊列維護候選字符。

完整可運行代碼

#include 
#include 
#include 
using namespace std;

char firstUnique(const char* s) {
    struct Node { int idx = -1, cnt = 0; } map[256];
    int len = strlen(s);
    for (int i = 0; i < len; ++i) {
        unsigned char c = s[i];
        if (map[c].idx == -1) map[c].idx = i;
        map[c].cnt++;
    }
    int best = INT_MAX;
    for (int i = 0; i < 256; ++i)
        if (map[i].cnt == 1) best = min(best, map[i].idx);
    return (best == INT_MAX) ? '\0' : s[best];
}

int main() {
    cout << firstUnique("1222345678234543") << endl; // 輸出 1
    return 0;
}