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

[shfshanyue]

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

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

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

[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
}

[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)

[shfshanyue]

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

[cyio]

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

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

[shfshanyue]

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

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

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

[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()
}

[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()
}

[shfshanyue]

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

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

[justorez]

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

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

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

[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
}

学到了，学到就是赚到 😄