字符串出现次数的TopK

题目描述

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

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

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

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

字符仅包含数字和字母

[要求]

如果字符串数组长度为N，时间复杂度请达到O(N \log K)O(NlogK)

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

备注:

$1 \leq N \leq 10^5$

堆

import java.util.*;
public class Solution {
    public String[][] topKstrings (String[] strings, int k) {
        Map<String,Integer> map = new HashMap<>();
        for(String s:strings){
            map.put(s,map.getOrDefault(s,0)+1);
        }
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for(Map.Entry<String,Integer> entry:map.entrySet()){
            Node node = new Node(entry.getKey(),entry.getValue());   
            if(pq.size()<k){
                pq.offer(node);
            }else{
                Node top = pq.peek();
                // 注意这里一定要用compareTo,否则需要比较两个,不然就是错误的
                if(top.compareTo(node)<0){
                    pq.poll();
                    pq.offer(node);
                }
            }
        }
        
        String [][] res = new String[k][2];
        int index = k-1;
        while(!pq.isEmpty()){
            Node node = pq.poll();
            res[index][0] = node.val;
            res[index][1] = String.valueOf(node.cnt);
            index--;
        }
        return res;
    }
    
    private class Node implements Comparable<Node>{
        String val;
        int cnt;
        public Node(String val,int cnt){
            this.val = val;
            this.cnt = cnt;
        }
        
        @Override
        public int compareTo(Node node){
            return this.cnt != node.cnt ? this.cnt-node.cnt : node.val.compareTo(this.val);
        }
    }
}

赏

谢谢你请我吃糖果

微信