DIV CSS 佈局教程網

JavaScript 找出字串中第一個不重複的字元
編輯:JavaScript綜合知識     

這是一個常見的面試題:給定一個字串,找出第一個只出現一次的字母。以下解法用最樸實的兩段式思路,不依賴任何進階技巧。

解法程式碼

// 找出字串中第一個不重複的字元
// 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 碼元。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved