給定字串,找出出現頻率最高的字元及其出現次數。例如 'adadfdfseffserfefsefseeffffftsdg' → 'f=11'。
function mostFrequentChar(str) {
if (!str) return { char: '', count: 0 };
const freq = new Map(); // 或 Object.create(null)
let maxChar = '';
let maxCount = 0;
for (const ch of str) {
const count = (freq.get(ch) || 0) + 1;
freq.set(ch, count);
if (count > maxCount) {
maxCount = count;
maxChar = ch;
}
}
return { char: maxChar, count: maxCount };
}
console.log(mostFrequentChar('adadfdfseffserfefsefseeffffftsdg'));
// { char: 'f', count: 11 }
function mostFrequentCharDestroy(str) {
let maxLength = 0;
let result = '';
while (str) {
const ch = str[0];
const newStr = str.replace(new RegExp(ch, 'g'), '');
const count = str.length - newStr.length;
if (count > maxLength) {
maxLength = count;
result = ch + '=' + maxLength;
}
str = newStr;
}
return result;
}
分析:每次 replace 掃描整個字串,時間複雜度 **O(k·n)**(k 為不同字元數),最壞 O(n²)。且修改原字串,不推薦生產環境使用。
function mostFrequentCharArray(str) {
const freq = new Array(65536).fill(0); // BMP 範圍
let maxChar = '', maxCount = 0;
for (let i = 0; i < str.length; i++) {
const code = str.charCodeAt(i);
const count = ++freq[code];
if (count > maxCount) { maxCount = count; maxChar = String.fromCharCode(code); }
}
return { char: maxChar, count: maxCount };
}
function mostFrequentCharUnicode(str) {
const freq = new Map();
let maxChar = '', maxCount = 0;
// 使用展開運算子正確處理 surrogate pairs
for (const ch of str) {
const count = (freq.get(ch) || 0) + 1;
freq.set(ch, count);
if (count > maxCount) { maxCount = count; maxChar = ch; }
}
return { char: maxChar, count: maxCount };
}
console.log(mostFrequentCharUnicode('😀😀😃😀a')); // { char: '😀', count: 3 }
| 方法 | 時間複雜度 | 空間複雜度 | Unicode 支援 | 備註 |
|---|---|---|---|---|
| Map 計數 | O(n) | O(k) | ✅ 完整 | 推薦通用方案 |
| 原文 replace 法 | O(k·n) ~ O(n²) | O(1) 額外 | ✅ | 教學示範,不推薦實用 |
| 陣列計數 | O(n) | O(65536) | ❌ 僅 BMP | 記憶體固定,適用高頻 ASCII |
| 展開運算子 + Map | O(n) | O(k) | ✅ 完整 | 正確處理 surrogate pairs |
function topKFrequent(str, k) {
const freq = new Map();
for (const ch of str) freq.set(ch, (freq.get(ch) || 0) + 1);
return [...freq.entries()].sort((a, b) => b[1] - a[1]).slice(0, k);
}
console.log(topKFrequent('abracadabra', 3)); // [['a',5], ['r',2], ['b',2]]