DIV CSS 佈局教程網

找出字串中出現次數最多的字符:一個不必轉陣列的巧妙解法
編輯:關於JavaScript     

「計算出字串中出現次數最多的字符是什麼,出現了多少次?」

看到這個題目,多數人的直覺是先把字串轉成陣列再做統計,這當然可行。但其實不必多此一舉,用一個簡短的迴圈搭配正則就能解決:

var str = "adadfdfseffserfefsefseeffffftsdg";
var maxLength = 0;
var result = "";
while (str != '') {
  oldStr = str;
  getStr = str.charAt(0);
  str = str.replace(new RegExp(getStr, "g"), "");
  if (oldStr.length - str.length > maxLength) {
    maxLength = oldStr.length - str.length;
    result = getStr + "=" + maxLength;
  }
}
alert(result);

演算法在思考什麼

核心思路是「一次性把同一個字符全部消滅」:

  1. 取出目前字串的第一個字元,記為 getStr。
  2. 用 replace 搭配 g 全域旗標,把字串中所有這個字元一次全部移除。
  3. 移除前後的長度差,就是這個字元出現的次數。
  4. 若這個次數刷新紀錄,就更新答案;迴圈在字串被清空時自然結束。

因為每一輪都能保證消掉至少一個字元,迴圈最多執行 n 次,且每次都要掃過剩下的字串,時間複雜度是 O(n²)。對短字串完全夠用,程式碼也夠簡潔;但若字串很長,還有更好的做法。

更直觀的做法:用物件當計數器

一次遍歷就能完成統計,時間複雜度降到 O(n):

var str = "adadfdfseffserfefsefseeffffftsdg";
var count = {};
var max = 0;
var result = '';

for (var i = 0; i < str.length; i++) {
  var ch = str.charAt(i);
  count[ch] = (count[ch] || 0) + 1;
  if (count[ch] > max) {
    max = count[ch];
    result = ch;
  }
}
alert(result + "=" + max);

兩種寫法各有適用的場合:前者在面試或教學情境中很能展現對 replace 與正則的掌握;後者則是實際專案中更值得採用的選擇。順帶一提,ES6 之後也可以改用 Map 來計數,語意更清楚,而且鍵值可以是任意型別,不受物件 key 只能是字串的鳥氣限制。

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