出现频率最高的字符

    题目描述

    给定一个字符串，找出其中出现频率最高的字符以及对应的出现次数。

    注意点：

    1. 字符串可能包含空格、符号或数字。
    2. 可能存在多个字符出现的频率并列最高，此时应当返回所有符合条件的字符。
    3. 如果字符串为空，应返回合理的默认值（如空数组和计数 0）。

    示例：

    • 输入: "aabbc" -> 输出: 频率为 2，字符为 ['a', 'b']
    • 输入: "apple" -> 输出: 频率为 2，字符为 ['p']

    思路分析

    核心的思路是利用哈希表或者字典来记录每个字符出现的次数，然后通过一次遍历找到最大值。即先统计，再筛选。

    1. 遍历字符串，用一个对象或者是 Map 记录每个字符出现的次数，用字符作为键，出现次数作为值。
    2. 在遍历过程中，维护两个变量记录出现次数最多的字符以及该字符出现的次数。分别记作 maxChar 和 maxCount。
    3. 每轮循环中，将字符出现的次数和 maxCount 进行比较和更新。

    解题方案

    export function getAllMostFrequentChars(str) {
  // 边界处理：如果传入的字符串为空（null、undefined 或空字符串），
  // 直接返回默认值，避免后续逻辑报错
  if (!str) {
    return { chars: [], count: 0 };
  }

  // 用一个普通对象充当"频率表"（哈希表）
  // 键是字符，值是该字符出现的次数
  // 例如 "aab" 遍历完后 charMap = { a: 2, b: 1 }
  const charMap = {};

  // maxCount：记录目前为止出现次数最多的字符的次数
  // 随着遍历不断更新
  let maxCount = 0;

  // 逐字符遍历整个字符串
  for (const char of str) {
    // 如果该字符已经出现过，次数 +1；否则初始化为 1
    // (charMap[char] || 0) 的作用：当 charMap[char] 为 undefined 时，取 0 作为初始值
    charMap[char] = (charMap[char] || 0) + 1;

    // 每次更新频率后，检查是否超过了当前记录的最大值
    // 如果是，就更新 maxCount
    if (charMap[char] > maxCount) {
      maxCount = charMap[char];
    }
  }

  // 遍历结束后，从频率表中筛选出所有出现次数等于 maxCount 的字符
  // 这样可以同时找出所有并列最高频的字符，而不只是第一个
  const result = Object.keys(charMap).filter(
    (char) => charMap[char] === maxCount,
  );

  // 返回结果对象：
  // chars —— 所有出现频率最高的字符组成的数组
  // count —— 最高频率是多少次
  return {
    chars: result,
    count: maxCount,
  };
}

// 测试案例
const testStr = 'aabbc';
const result = getAllMostFrequentChars(testStr);

console.log(`最高频率为: ${result.count}`);
console.log(`对应的字符有: ${result.chars.join(', ')}`);
// 输出: 最高频率为: 2, 对应的字符有: a, b

    复杂度分析

    1. 时间复杂度是 O(n)。主要是对字符串的遍历，虽然使用了 Object.keys 和 filter，但这是属于对频率表的二次遍历，它通常远小于字符串的长度。
    2. 空间复杂度是 O(k)。用于存储频率表和结果数组。

    进阶优化

    使用更现代的风格对代码进行重构，让代码看起来更简洁，更高级。

    两次 reduce
    一次 reduce
    export function getMostFrequentChars(str) {
  // 边界处理：空字符串、null、undefined 时直接返回默认值
  if (!str) {
    return { chars: [], count: 0 };
  }

  // 第一步：用 reduce 构建频率表（Map）
  // [...str] 将字符串拆分为字符数组，例如 'ab' => ['a', 'b']
  // reduce 从左到右遍历每个字符，acc 是累加器（这里是一个 Map）
  const charMap = [...str].reduce((acc, char) => {
    // acc.get(char) 取出该字符当前计数，若还没出现过则为 undefined，|| 0 使其初始为 0
    // 然后 +1，再用 acc.set 写回 Map
    acc.set(char, (acc.get(char) || 0) + 1);
    // 必须 return acc，让下一次迭代继续使用同一个 Map
    return acc;
  }, new Map()); // new Map() 是累加器的初始值（空频率表）

  // 第二步：遍历频率表，找出出现次数最多的字符
  // [...charMap] 将 Map 转为 [[char, count], ...] 形式的数组
  return [...charMap].reduce(
    (res, [char, count]) => {
      // 如果当前字符的次数 > 已记录的最大值，说明找到了新的最高频字符
      // 用新字符替换结果，重置 chars 数组
      if (count > res.count) {
        return { chars: [char], count };
      } else if (count === res.count) {
        // 次数与当前最大值相同，是并列最高频，追加到 chars 数组
        res.chars.push(char);
      }
      // 次数更小则忽略，直接返回未修改的 res
      return res;
    },
    { chars: [], count: 0 }, // 初始结果：空字符列表，最大计数为 0
  );
}

// 测试
const { chars, count } = getMostFrequentChars('mississippi');
console.log(`最高频次: ${count}, 字符: ${chars}`);
// 输出: 最高频次: 4, 字符: i, s

    上述代码为什么显得 “高级” ？

    1. 使用解构赋值、展开运算符、Map、reduce 等更现代的语法和 API。
    2. 所有的逻辑都封装在数据转换的过程中，而不是通过修改外部变量来完成。
    3. 它是一段声明式逻辑，它告诉程序 “我要把这个对象 reduce 成一个结果”，而不是让机器 “先做第一步，再做第二步”。

    注意：虽然这 reduce 用起来很简洁，但是面对超大规模数据时，传统的 for..of 循环性能会更好。

    问题扩展

    当需求从 “找第 1 名” 变为 “找前 n 名” 时，问题的性质就从简单的最大值变成了排序或堆的问题了。

    核心思路：

    1. 统计频率，依然使用 Map 记录每个字符出现的次数。
    2. 转换为数组，将 Map 转换为键值对数组。
    3. 排序，依据出现的次数对数组进行降序排序。
    4. 截取出排序后的前 n 个元素。

    常规解法

    // 函数：返回字符串 str 中出现频率最高的前 n 个字符
// 参数 str：要统计的字符串；参数 n：取前几名
// 返回值：[{ char, count }, ...] 形式的数组，按出现次数从多到少排列
export function getTopNChars(str, n) {
  // 边界守卫：
  //   !str           —— str 为空字符串、null 或 undefined 时直接返回空数组
  //   !Number.isInteger(n) —— n 必须是整数，排除 undefined / NaN / 小数等非法值
  //   n <= 0         —— n 必须大于 0，否则"前 0 名"没有意义
  if (!str || !Number.isInteger(n) || n <= 0) {
    return [];
  }

  // 第一步：构建字符频率表（Map）
  // [...str] 利用字符串迭代器将字符串拆成单个字符的数组
  //   例如 'abc' => ['a', 'b', 'c']，能正确处理 emoji 等多字节字符
  // .reduce(回调, 初始值) 从左到右遍历数组，把结果累积到 acc 中
  //   初始值 new Map() 是一个空的键值对映射表，用来存 { 字符 => 出现次数 }
  const charMap = [...str].reduce((acc, char) => {
    // acc.get(char) 取出该字符目前的计数，若从未出现过则返回 undefined
    // || 0 把 undefined 转为 0，保证后续 +1 不会产生 NaN
    // acc.set(char, ...) 将新计数写回 Map，完成一次"计数 +1"
    acc.set(char, (acc.get(char) || 0) + 1);
    // 必须 return acc，让下一次迭代继续使用同一个 Map
    return acc;
  }, new Map()); // new Map() 是累加器的初始值（空频率表）

  // 第二步：排序 → 截取前 n 名 → 格式化输出，三步链式调用
  return [...charMap] // 将 Map 转为 [[char, count], ...] 二维数组，方便排序
    .sort((a, b) => b[1] - a[1]) // 按 count（索引 1）从大到小排序：b[1] - a[1] > 0 时 b 排前面
    .slice(0, n) // 只保留前 n 个元素（索引 0 到 n-1）
    .map(([char, count]) => ({ char, count })); // 将 [char, count] 解构为 { char, count } 对象，更易读
}

// 测试：找出字符串 "aabbbccccddddd" 中出现次数前 3 的字符
const result = getTopNChars('aabbbccccddddd', 3);
console.log(result);
/* 输出: 
[
  { char: 'd', count: 5 },
  { char: 'c', count: 4 },
  { char: 'b', count: 3 }
]
*/

    虽然这个代码看起简洁，但是存在一些性能问题。首先统计频率的时间复杂度为 O(n)，在排序阶段假设有 m 个不重复的字符，由于 sort 的时间复杂度为 O(mlogm)。这样一来，整体的复杂度来到了 O(k + mlogm)。

    如果字符串非常大，但是我们只需要前三名，用 sort 去排序就会很浪费。

    小顶堆解法

    可以采用小顶堆(Min-Heap)来进行优化。维护一个大小只有 n 的小顶堆，遍历频率表的时候，如果当前字符频率比堆顶大，就替换堆顶并重新调整。

    这样可以将复杂度降低到 O(mlogn)。由于 n 远小于 m，这在处理超长字符时更有优势。

    为什么选用小顶堆来找 “最大” ？

    想象一个只有 n 个座位的房间，我们需要找到最强的 n 个人:

    1. 让前 n 个人进去。
    2. 用里面最弱的那个人（堆顶）守在大门口。
    3. 门来每来一个新人，只跟门里最弱的那个人比较。
    4. 如果新人更强，就把最弱的踢走，新人进去。
    5. 最后房间里剩下的就是最强的 n 个人。

    注：如果使用大顶堆，则需要对所有的数据进行堆排序后才能知道哪些是最大的。

    最小堆解法
    实现最小堆
    import { Heap } from './index.js';

function topKFrequentChars(str, n) {
  if (!str || n <= 0) {
    return [];
  }

  // 初始化 map 并统计字符出现的频率到哈希表
  const charMap = [...str].reduce((acc, char) => {
    acc.set(char, (acc.get(char) || 0) + 1);
    return acc;
  }, new Map());

  // 初始化堆，传入自定义比较函数
  // 如果对象 a 的 count 小于对象 b 的 count 时
  // 即 A - B < 0, 时，a 会 排在 b 的前面
  // 多次操作之后若 a 最小，则会浮到堆顶。
  const minHeap = new Heap((a, b) => a.count - b.count);

  // 遍历哈希表，逐个推入堆里
  for (const [char, count] of charMap) {
    // 逐个推入堆里，维护长度为 n 的堆
    minHeap.push({ char, count });
    // 如果堆的长度大于 n，则需要取出最小的（堆顶的元素）
    if (minHeap.size() > n) {
      minHeap.pop();
    }
  }

  // 提取结果
  const res = [];
  while (!minHeap.isEmpty()) {
    const item = minHeap.pop();
    if (item) {
      res.push(item);
    }
  }

  // 按照从大到小返回
  return res.reverse();
}

const text = 'javascriptisawesomeee';
const k = 3;
console.log(`Top ${k} characters:`, topKFrequentChars(text, k));