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

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

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

Issue 欢迎在 Gtihub Issue 中回答此问题: Issue 652

Author 回答者: shfshanyue

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

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

// 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);

Author 回答者: shfshanyue

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

Author 回答者: cyio

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

什么复杂度，时间？sort 更快

Author 回答者: shfshanyue

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

什么复杂度，时间？sort 更快

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

Author 回答者: cyio

恩，你说的是对的。不过，实际在 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

恩，你说的是对的。不过，实际在 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 回答者: shfshanyue

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

Author 回答者: shengrongchun

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

Author 回答者: justorez

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

什么复杂度，时间？sort 更快

做题看时间复杂度就行了吧，实际环境v8有各种优化，就说不清了。

Author 回答者: Hazel-Lin

console.log(getFrequentChar("aacc"));
console.log(getFrequentChar("aaccccaaaa"));
console.log(getFrequentChar("baaaabbcc"));
 
function getFrequentChar(string) {
  let obj = {};
  let maxStr = ["", 0];
  for (const char of string) {
    obj[char] = (obj[char] || 0) + 1;
    // obj[char] ? obj[char]++ : (obj[char] = 1)
    if (obj[char] > maxStr[1]) {
      maxStr = [char, obj[char]];
    } else if (obj[char] === maxStr[1]) {
      maxStr = maxStr.concat([char, obj[char]]);
    }
  }
  return maxStr;
}

学到了，学到就是赚到 😄

【Q629】实现一个函数 max，找到数组中最大的一个值/两个值/N个值【Q635】请输出 100 以内的菲波那切数列