# 统计字符串中出现次数最多的字符及次数
更多描述
这是一道大厂面试出现频率超高的编程题
//=> ['a', 6]
getFrequentChar("aaabbaaacc");
//=> ['a', 3]
getFrequentChar("aaa");
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 652 (opens new window)
Author
见代码实现: 统计字符串中出现次数最多的字符及次数- 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
// 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
@cyio 使用 sort 复杂度立马就上去了
Author
@cyio 使用 sort 复杂度立马就上去了
什么复杂度，时间？sort 更快
Author
@cyio 使用 sort 复杂度立马就上去了
什么复杂度，时间？sort 更快
sort 时间复杂度肯定就上去了，它内部的时间复杂度 O(nlogn)，肯定没有手写 maxBy，只需要 On 的复杂度
Author
恩， 你说的是对的。不过，实际在 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
恩， 你说的是对的。不过，实际在 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 我试了下，把关于 r/r2 的代码调换下顺序，结果就相反了，明天我搞一个两方各执行一万次的 benchmark 试一试
Author
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];
}