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