這是一個常見的面試題:給定一個字串,找出第一個只出現一次的字母。以下解法用最樸實的兩段式思路,不依賴任何進階技巧。
// 找出字串中第一個不重複的字元
// firstUniqueChar("vdctdvc"); --> t
function firstUniqueChar(str){
var str = str || "",
i = 0,
k = "",
_char = "",
charMap = {},
result = { name: "", index: str.length };
for(i = 0; i < str.length; i++){
_char = str.charAt(i);
if(charMap[_char] != undefined){
charMap[_char] = -1; // 第二次出現,標記為重複
} else {
charMap[_char] = i; // 第一次出現,記錄索引
}
}
for(k in charMap){
if(charMap[k] < 0){
continue; // 跳過已標記為重複的字元
}
if(result.index > charMap[k]){
result.index = charMap[k];
result.name = k;
}
}
return result.name;
}
第一趟迴圈建立一個對照表 charMap:字元第一次出現時,把它的索引位置存進去;第二次以後出現,就把值改成 -1 代表「這是不重複的」。第二趟迴圈走訪對照表,跳過所有值為負的項目,在剩下的候選中挑出索引最小的那一個——索引最小,就是位置最前面的意思。
以 "vdctdvc" 為例:v、d、c 都出現兩次被標成 -1,只有 t 保留著它的索引 3,因此回傳 t。
這個解法時間複雜度是 O(n),但用了兩趟迴圈與一個額外雜湊表,空間 O(n)。如果追求更簡潔的現代寫法,可以這樣做:
function firstUniqueChar(str) {
for (const ch of str) {
if (str.indexOf(ch) === str.lastIndexOf(ch)) return ch;
}
return "";
}
用 indexOf 與 lastIndexOf 相等來判斷「只出現一次」,程式碼短很多、意圖也更清楚,代價是每次判斷都要掃描字串,最壞情況會退化為 O(n²)。字串長度不大時兩者差異不明顯,資料量大時仍以雜湊表版本為佳。另外若字串可能包含 emoji 或代理組合字元,用 for...of 或 Array.from() 迭代才能正確以「使用者看到的那個字」為單位,而非 UTF-16 碼元。