字符串出现次数的TopK问题

[编程题]字符串出现次数的TopK问题

热度指数：44027 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串数组，再给定整数 k ，请返回出现次数前k名的字符串和对应的次数。

返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。

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

比如"ah1x"小于"ahb"，"231"<”32“

字符仅包含数字和字母

数据范围：字符串数满足 $0 \le n \le 100000$ ，每个字符串长度 $0 \le n \le 10$ ， $0 \le k \le 2500$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n \log k)$

示例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"]]

备注:

算法知识视频讲解

Typescript

gai溜子

export function topKstrings(strings: string[], k: number): string[][] {
    // write code here
    let obj = {},target = [];
    strings.forEach( item => obj[item] = Reflect.has(obj,item) ? ++obj[item] : 1 );
    for(let key in obj){
        target.push([...[key,obj[key]]]);
    }
    target.sort();
    target.sort((a,b) => b[1] - a[1]);
    return target.slice(0,k);
}

发表于 2021-08-27 10:45:20 回复(0)