极客时间返利平台,你可以在上边通过山月的链接购买课程,并添加我的微信 (shanyue94) 领取返现。

# 统计字符串中出现次数最多的字符及次数

更多描述

这是一道大厂面试出现频率超高的编程题

//=> ['a', 6]
getFrequentChar("aaabbaaacc");

//=> ['a', 3]
getFrequentChar("aaa");

Issue

欢迎在 Gtihub Issue 中回答此问题: Issue 652 (opens new window)

见代码实现: 统计字符串中出现次数最多的字符及次数- codepen (opens new window)

function getFrequentChar(str) {
  const dict = {};
  for (const char of str) {
    dict[char] = (dict[char] || 0) + 1;
  }
  const maxBy = (list, keyBy) =>
    list.reduce((x, y) => (keyBy(x) > keyBy(y) ? x : y));
  return maxBy(Object.entries(dict), (x) => x[1]);
}

以下方案一边进行计数统计一遍进行大小比较,只需要 1 次 O(n) 的算法复杂度

function getFrequentChar2(str) {
  const dict = {};
  let maxChar = ["", 0];
  for (const char of str) {
    dict[char] = (dict[char] || 0) + 1;
    if (dict[char] > maxChar[1]) {
      maxChar = [char, dict[char]];
    }
  }
  return maxChar;
}

Author

回答者: cyio (opens new window)

// entries + sort
function getFrequentChar(str) {
  const dict = {};
  for (const char of str) {
    dict[char] = (dict[char] || 0) + 1;
  }
  let list = Object.entries(dict);
  list.sort((a, b) => b[1] - a[1]);
  return list[0];
}

// test
let r = getFrequentChar("aaabccd");
console.log(r);

@cyio 使用 sort 复杂度立马就上去了

Author

回答者: cyio (opens new window)

@cyio 使用 sort 复杂度立马就上去了

什么复杂度,时间?sort 更快

@cyio 使用 sort 复杂度立马就上去了

什么复杂度,时间?sort 更快

sort 时间复杂度肯定就上去了,它内部的时间复杂度 O(nlogn),肯定没有手写 maxBy,只需要 On 的复杂度

Author

回答者: cyio (opens new window)

恩, 你说的是对的。不过,实际在 chrome/node 中执行,发现 sort 大部分情况下更快。

let s = function () {
  function getFrequentChar(str) {
    const dict = {};
    for (const char of str) {
      dict[char] = (dict[char] || 0) + 1;
    }
    const maxBy = (list, keyBy) =>
      list.reduce((x, y) => (keyBy(x) > keyBy(y) ? x : y));
    return maxBy(Object.entries(dict), (x) => x[1]);
  }

  function getFrequentCharSort(str) {
    const dict = {};
    for (const char of str) {
      dict[char] = (dict[char] || 0) + 1;
    }
    let list = Object.entries(dict);
    //     console.log(list)
    list.sort((a, b) => b[1] - a[1]);
    return list[0];
  }

  function generateRamStr(len, charSet) {
    const chars =
      charSet ||
      "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    let randomStr = "";
    for (var i = 0; i < len; i++) {
      randomStr += chars.charAt(Math.floor(Math.random() * chars.length));
    }
    return randomStr;
  }

  let str = generateRamStr(10 ** 5);
  // console.log(str)

  // test
  console.time("reduce");
  let r = getFrequentChar(str);
  console.timeEnd("reduce");
  //  console.log(r)

  console.time("sort");
  let r2 = getFrequentCharSort(str);
  console.timeEnd("sort");
  // console.log(r2)
};

for (let i = 0; i < 10; i++) {
  s();
}

Author

回答者: cyio (opens new window)

恩, 你说的是对的。不过,实际在 chrome/node 中扫行,发现 sort 大部分情况下更快。

let s = function () {
  function getFrequentChar(str) {
    const dict = {};
    for (const char of str) {
      dict[char] = (dict[char] || 0) + 1;
    }
    const maxBy = (list, keyBy) =>
      list.reduce((x, y) => (keyBy(x) > keyBy(y) ? x : y));
    return maxBy(Object.entries(dict), (x) => x[1]);
  }

  function getFrequentCharSort(str) {
    const dict = {};
    for (const char of str) {
      dict[char] = (dict[char] || 0) + 1;
    }
    let list = Object.entries(dict);
    //     console.log(list)
    list.sort((a, b) => b[1] - a[1]);
    return list[0];
  }

  function generateRamStr(len, charSet) {
    const chars =
      charSet ||
      "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    let randomStr = "";
    for (var i = 0; i < len; i++) {
      randomStr += chars.charAt(Math.floor(Math.random() * chars.length));
    }
    return randomStr;
  }

  let str = generateRamStr(10 ** 5);
  // console.log(str)

  // test
  console.time("reduce");
  let r = getFrequentChar(str);
  console.timeEnd("reduce");
  //  console.log(r)

  console.time("sort");
  let r2 = getFrequentCharSort(str);
  console.timeEnd("sort");
  // console.log(r2)
};

for (let i = 0; i < 10; i++) {
  s();
}

@cyio 我试了下,把关于 r/r2 的代码调换下顺序,结果就相反了,明天我搞一个两方各执行一万次的 benchmark 试一试

function longStr(str) {
  let results = [];
  for (let key of str) {
    const reg = new RegExp(key, "g");
    const arr = str.match(reg) || [];
    if (arr.length > results.length) {
      results = arr;
    }
  }
  return [results[0], results.length];
}
Last Updated: 6/26/2022, 10:48:10 AM