哈希表频数统计

如何用频数表求多数元素？

• 思路: 遍历数组建立"元素 → 出现次数"的映射;
• 判定: 出现次数大于 ⌊n / 2⌋ 的元素即多数元素;
• 复杂度: 时间 O(n), 空间 O(n);

function majorityElement(nums: number[]): number | undefined {
  const count = new Map<number, number>();
  for (const num of nums) {
    count.set(num, (count.get(num) ?? 0) + 1);
  }
  for (const [num, times] of count) {
    if (times > Math.floor(nums.length / 2)) return num;
  }
}

如何用频数差判断字母异位词？

• 字母异位词: 两个字符串的字符种类与数量完全相同, 顺序可以不同;
• 思路: 遍历 s 累加频数, 遍历 t 扣减频数;
• 判定: 扣减出现负数说明 t 多出该字符; 长度不同可直接返回 false;
• 复杂度: 时间 O(m + n), 空间 O(字符集大小);

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;

  const count = new Map<string, number>();
  for (const ch of s) count.set(ch, (count.get(ch) ?? 0) + 1);

  for (const ch of t) {
    const rest = (count.get(ch) ?? 0) - 1;
    if (rest < 0) return false;
    count.set(ch, rest);
  }
  return true;
}

如何用频数奇偶判断最长回文串？

• 回文串构成: 所有字符成对出现, 至多一个字符出现奇数次并放在中间;
• 思路: 统计频数, 每个字符取不超过频数的最大偶数累加;
• 补充: 只要存在频数为奇数的字符, 结果再 +1 作为中心字符;
• 复杂度: 时间 O(n), 空间 O(字符集大小);

function longestPalindrome(s: string): number {
  const count = new Map<string, number>();
  for (const ch of s) count.set(ch, (count.get(ch) ?? 0) + 1);

  let length = 0;
  let hasOdd = false;
  for (const times of count.values()) {
    length += times - (times % 2);
    if (times % 2 === 1) hasOdd = true;
  }
  return hasOdd ? length + 1 : length;
}