給定字串,找出第一個只出現一次的字元。這是經典面試題,也是實務中字元統計的基礎操作。本文提供三種解法:暴力法、雜湊表單趟、雜湊表雙趟,並分析時間/空間複雜度與實測效能。
firstUniqueChar("vdctdvc") // → 't'
firstUniqueChar("aabbcc") // → null 或 ''
firstUniqueChar("") // → null
function firstUniqueCharBrute(str) {
for (let i = 0; i < str.length; i++) {
let found = false;
for (let j = 0; j < str.length; j++) {
if (i !== j && str[i] === str[j]) {
found = true;
break;
}
}
if (!found) return str[i];
}
return null;
}
function firstUniqueChar(str) {
if (!str) return null;
const count = new Map(); // 或 Object
// 單趟統計 + 記錄首次索引
for (let i = 0; i < str.length; i++) {
const ch = str[i];
if (count.has(ch)) {
count.get(ch).count++;
} else {
count.set(ch, { count: 1, firstIndex: i });
}
}
// 找出 count=1 且 firstIndex 最小者
let result = null;
let minIndex = Infinity;
for (const [ch, info] of count) {
if (info.count === 1 && info.firstIndex < minIndex) {
minIndex = info.firstIndex;
result = ch;
}
}
return result;
}
優化點:單趟統計同時記錄首次索引,第二趟遍歷 Map (最多 65536 個 Unicode 字元) 而非原字串。
function firstUniqueCharTwoPass(str) {
const freq = {};
// 第一趟:統計頻率
for (const ch of str) {
freq[ch] = (freq[ch] || 0) + 1;
}
// 第二趟:找第一個頻率為 1
for (const ch of str) {
if (freq[ch] === 1) return ch;
}
return null;
}
const longStr = 'a'.repeat(500000) + 'b' + 'c'.repeat(499999); // 'b' 為唯一不重複
console.time('brute');
firstUniqueCharBrute(longStr.slice(0, 1000)); // 僅測前1000,完整會跑太久
console.timeEnd('brute'); // ~45ms (僅1000字元)
console.time('two-pass');
firstUniqueCharTwoPass(longStr);
console.timeEnd('two-pass'); // ~8ms
console.time('single-pass-map');
firstUniqueChar(longStr);
console.timeEnd('single-pass-map'); // ~10ms (Map 開銷稍大)
// 字串迴圈會正確處理 Unicode 代理對
for (const ch of "👨👩👧👦") {
console.log(ch); // 正確輸出單一字素簇
}
// 但 charAt/charCodeAt 會拆分代理對
"👨👩👧👦".charAt(0); // "\uD83D" (高代理)
"👨👩👧👦"[0]; // "\uD83D"
// 解決:使用展開運算子或 Array.from
[..."👨👩👧👦"]; // ["👨👩👧👦"] 正確
若字串來自串流或極大檔案,無法一次載入記憶體:
async function firstUniqueCharStream(stream) {
const freq = new Map();
const order = []; // 記錄首次出現順序
for await (const chunk of stream) {
for (const ch of chunk) {
if (!freq.has(ch)) {
freq.set(ch, 1);
order.push(ch);
} else {
freq.set(ch, freq.get(ch) + 1);
}
}
}
for (const ch of order) {
if (freq.get(ch) === 1) return ch;
}
return null;
}
| 解法 | 時間複雜度 | 空間複雜度 | 程式碼複雜度 | 實務推薦度 |
|---|---|---|---|---|
| 暴力雙重迴圈 | O(n²) | O(1) | 低 | ❌ 僅教學 |
| 雜湊表雙趟 | O(n) | O(k) | 低 | ✅✅✅ 首選 |
| 雜湊表單趟+索引 | O(n) | O(k) | 中 | ✅✅ 大字串優勢不明顯 |
// 利用 find + filter (較慢但極簡)
const firstUnique = s => [...s].find(c => s.indexOf(c) === s.lastIndexOf(c));
// 或 reduce 單趟 (較難讀)
const firstUnique = s => [...s].reduce((a,c,i) => a.set(c, (a.get(c)||0)+1), new Map())
&& [...s].find(c => freq.get(c)===1);
實務上 **雜湊表雙趟** 最佳平衡:可讀性高、效能優、易維護。理解 Map/Object 差異、Unicode 處理、串流擴展,才能應對各種變體題目。