NC97.字符串出现次数的TopK问题

描述

给定一个字符串数组，再给定整数 k ，请返回出现次数前k名的字符串和对应的次数。返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。

对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。

比如"ah1x"小于"ahb"，"231"<”32“，字符仅包含数字和字母

示例1

输入：["a","b","c","b"], 2
返回值：[["b","2"],["a","1"]]
说明： "b"出现了2次，记["b","2"]，"a"与"c"各出现1次，
但是a字典序在c前面，记["a","1"]，最后返回[["b","2"],["a","1"]]

示例2

输入：["123","123","231","32"], 2
返回值：[["123","2"],["231","1"]]
说明："123"出现了2次，记["123","2"]，"231"与"32"各出现1次，
但是"231"字典序在"32"前面，记["231","1"]，最后返回[["123","2"],["231","1"]]   

示例3

输入：["abcd","abcd","abcd","pwb2","abcd","pwb2","p12"],3
返回值：[["abcd","4"],["pwb2","2"],["p12","1"]]

题解：

/**
 * return topK string
 * @param strings string字符串一维数组 strings
 * @param k int整型 the k
 * @return string字符串二维数组
 */
function topKstrings(strings, k) {
  // 创建一个对象
  let obj = {};
  // 结果数组
  let res = [];
  // 将给定的数组排序
  strings.sort();
  
  // 遍历给定的数组
  for (let i = 0; i < strings.length; i++) {
    // 判断对象中有这个元素 这个元素 数值加1
    if (obj.hasOwnProperty(strings[i])) {
      obj[strings[i]]++;
    } else {
      // 否则将这个key变为1
      obj[strings[i]] = 1;
    }
  }
  
  // 将所有的元素映射之后 遍历对象 构造二维数组
  for (var key in obj) {
    let arr2 = [];
    arr2.push(key, obj[key]);
    res.push(arr2);
  }
  // 构造完毕数组之后 对最终的结果进行二次排序
  res.sort(function (a, b) {
    if (a[1] == b[1]) {
      if (a[0] < b[0]) return -1;
      else return 1;
    } else {
      return b[1] - a[1];
    }
  });
  // 截取前k个
  res.splice(k);
  // 返回结果
  return res;
}
module.exports = {
  topKstrings: topKstrings,
};