DIV CSS 佈局教程網

統計字串中每個字元出現次數: from 排序到累加的完整實作
編輯:關於JavaScript     

「給你一個字串,算出每個字元出現幾次」是面試常見題。看起來朴素,但它同時考驗了 split、sort 與物件聚合的運用。本文給出一個不依賴任何函式庫的完整實作。

運行結果:

程式碼:

 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="https://www.w3.org/1999/xhtml">
<head>
<title>求字符串中每个字符出现的次数</title>
<script type="text/javascript">
var str = "abdcadfasfdbadfafdasdfasyweroweurowqrewqrwqrebwqrewqrejwq;;";
var array = str.split("");
array.sort();               // 相同字元會被排在一起

var countArray = [];
var CountObj = function (character) {
    this.count = 1;
    this.character = character;
    return this;
};

var arrayObj = null, countArrayObj = null, arrayLength = 0;

for (var i = 0, length = array.length; i < length; i++) {
    arrayObj = array[i];
    arrayLength = countArray.length;
    if (arrayLength > 0) {
        countArrayObj = countArray[arrayLength - 1];
        // 與上一筆相同就累加,否則新增一筆
        if (countArrayObj.character == arrayObj) {
            countArrayObj.count = countArrayObj.count + 1;
        } else {
            countArray.push(new CountObj(arrayObj));
        }
    } else {
        countArray.push(new CountObj(arrayObj));
    }
}

// 輸出每個字母與對應的統計結果
for (var i = 0, length = countArray.length; i < length; i++) {
    countArrayObj = countArray[i];
    console.log(countArrayObj.character + ":" + countArrayObj.count);
}
</script>
</head>
<body>
</body>
</html> 

這個解法的核心是一個觀察:排序之後,相同的字元必然相鄰。既然相鄰,就不需要每次都去整份統計表裡翻找,只要跟「最後一筆」比對即可。這一步把原本 O(n²) 的查找,降成了單次遍歷。

幾個可以延伸思考的點:

為什麼用陣列裝物件,而不是直接用物件當計數器?用 {} 做 key 計數當然更短,但物件屬性有原型鏈的顧慮(例如字元剛好叫 constructor),而且輸出的順序不保證與字元出現順序一致。用陣列配一個簡單的 CountObj,順序與內容都在掌控之中。

排序帶來了副作用。因為先 sort,輸出的順序是依字元碼排列,而非首次出現順序。如果需求是「依首次出現順序輸出」,就應該改用 Map 或物件累加,並額外記錄首次出現的索引。

大小寫與空白怎麼算?範例直接統計原始字元,所以大寫小寫視為不同。實務上通常會先 toLowerCase(),並視需求過濾掉空白與標點符號。

把這幾個變形想清楚,這道題就從「背一個解法」變成「知道為什麼這樣解」了。

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