DIV CSS 佈局教程網

用 JavaScript 找出字符串中第一個不重複的字符
編輯:關於JavaScript     

以下演算法僅供參考。用最直接的想法來解:先掃一輪記錄每個字符出現的位置,重複出現的標記為 -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 "";
}

邏輯更直白,也不依賴物件的鍵枚舉順序。若有更好的思路,歡迎一起交流。

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