以下演算法僅供參考。用最直接的想法來解:先掃一輪記錄每個字符出現的位置,重複出現的標記為 -1;再回頭找出位置值最小且未被標記的字符。
// 找出字符串中第一個不重複的字符
// firstUniqueChar("vdctdvc"); --> "t"
function firstUniqueChar(str) {
var str = str || "",
i = 0,
k = "",
_char = "",
charMap = {},
result = { name: "", index: str.length };
// 第一輪:記錄首次出現位置,重複者標記為 -1
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;
}
這個做法時間複雜度是 O(n),但用了兩次遍歷,而且 for/in 的枚舉順序在不同引擎下不保證,因此才需要額外比對 index 來確保結果正確。
如果想寫得更簡潔,可以用 Map 一次搞定——利用 Map 保留插入順序的特性,直接回傳第一個計數為 1 的鍵:
function firstUniqueChar(str) {
var count = new Map();
for (var i = 0; i < str.length; i++) {
var ch = str[i];
count.set(ch, (count.get(ch) || 0) + 1);
}
for (var entry of count) {
if (entry[1] === 1) return entry[0];
}
return "";
}
邏輯更直白,也不依賴物件的鍵枚舉順序。若有更好的思路,歡迎一起交流。