萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 找出字串中出現次數最多的字元與次數(O(n) 演算法)

問題描述

給定字串,找出出現頻率最高的字元及其出現次數。例如 'adadfdfseffserfefsefseeffffftsdg' → 'f=11'。

方案一:哈希表計數(標準 O(n))

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²)。且修改原字串,不推薦生產環境使用。

方案三:陣列計數(適用於 ASCII / BMP 字元)

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 };
}

方案四:支援完整 Unicode(含 Emoji、罕用字)

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
展開運算子 + MapO(n)O(k)✅ 完整正確處理 surrogate pairs

延伸:Top K 高頻字元

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]]
copyright © 萬盛學電腦網 all rights reserved