首页 > 试题广场 >

字符串出现次数的TopK问题

[编程题]字符串出现次数的TopK问题
  • 热度指数:43891 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个字符串数组,再给定整数 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"]]

备注:
from collections import defaultdict

class Solution:
    def topKstrings(self , strings , k ):
        # write code here
        cnt = defaultdict(int)
        for s in strings:
            cnt[s] += 1
        
        stat = sorted(cnt.items(), key=lambda tp: (-tp[1], tp[0]))[:k]
        return [[k, str(n)] for k, n in stat]
    

发表于 2021-03-24 23:12:30 回复(0)
from collections import  Counter
class Solution:
    def topKstrings(self , strings , k ):
      c = Counter(strings)
      d = sorted(c.items(), key = lambda x: (-x[1],x[0]))
      return d[:k]

发表于 2021-07-05 16:00:15 回复(0)
class Solution {
public:
    /**
     * return topK string
     * @param strings string字符串vector strings
     * @param k int整型 the k
     * @return string字符串vector<vector<>>
     */
    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        //先用int计数 然后再用to_string把它转换成字符串
        map<string, int> mp;
        vector<vector<string>> res;
        
        for(const auto &i : strings){
            mp[i]++;
        }
        for(auto it = mp.begin(); it != mp.end(); it++){
            res.push_back( {it->first,to_string(it->second)} );
        }
        
        /*sort(word.begin(),words.end(),
        [](const string &a, const string &b){
        return a.size() < b.size();
    });*/
        sort(res.begin(), res.end(),
             [](vector<string> &m, vector<string> &n){
            //如果是mp[0]=1;mp[1]=1
                 if(m[1] == n[1]){
                     return m[0] < n[0];
                 } else { //mp[1] = '2' mp[2] = '1' 得把'2'变成 2
                     return stoi(m[1]) > stoi(n[1]);
                 }
                 
        });
        
        //重新赋大小 不重新赋大小 会多出["3","1"]
        res.resize(k);
        return res;
    }
};

发表于 2021-03-31 20:48:26 回复(1)
import java.util.*;


public class Solution {
    /**
     * 题意要求是TopK问题,时间复杂度达到O(NlogK),并且相同大小要按字典排序,
     * 所以排序方法应该是堆排序或者快速选择排序。
     * 这里排序使用小顶堆,按值排序时是从小到大。当值相同时,比较str,这里重写堆节点的比较方法,
     * 值相同时,str字典序大的先入堆。
     * 最后,排序好的小顶堆输出k个数到结果集,结果集数组从尾部开始填充,
     * 这样小顶堆的数据刚好逆序,在结果集里的表现就是 按值排序是升序,值相同是字典小的在数组前面。
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    public String[][] topKstrings (String[] strings, int k) {
       
        if(strings==null || strings.length==0){
            return null;
        }
        
        HashMap<String,Integer> map = new HashMap();
        for(String s : strings){
            //初始化 数组中每个字符串默认出现一次
            map.put(s,map.getOrDefault(s,0)+1);
        }
        
        // 优先队列,实现小顶堆,输出到结果集就是堆的逆序,即倒序输出小顶堆,即大顶堆
        //https://blog.csdn.net/wufaliang003/article/details/82940218参考最小堆的思想
        PriorityQueue<Node> minHeap = new PriorityQueue();
        for(Map.Entry<String,Integer> entrySet : map.entrySet()){
            Node node = new Node(entrySet.getKey(),entrySet.getValue());
            //先用前k个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的k个元素。
            if(minHeap.size() < k){
                minHeap.add(node);
            }else{
                // 堆中元素等于 k 个时
                // 当 node的值大于栈顶元素,或者值相同时node的字典小于栈顶元素 时(最小堆构建规则,就是如此)
                //这相当于上一个条件:先用前k个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的k个元素。
                //接着,从第k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,
                //以保证堆内的k个元素,总是当前最大的k个元素。
                if(minHeap.peek().compareTo(node) < 0){
                    minHeap.poll();
                    minHeap.add(node);
                }
            }
        }
        
        String[][] result = new String[k][2];
        //正序弹出小顶堆上面的元素,数组逆序输出
        for(int i=k-1;i>=0;i--){
            Node node = minHeap.poll();
            result[i][0] = node.name;
            result[i][1] = String.valueOf(node.count); 
        }
        return result;
    }
    
    class Node implements Comparable<Node>{
        
        //对应上面Map里的key
        String name;
        //对应上面Map里的value
        int count;
        
        public Node(String name,int count){
            this.name = name;
            this.count = count;
        }
        
        @Override
        public int compareTo(Node node){
            //正常是通过Node对象里的count来比较大小的
            if(this.count > node.count){
                return 1;
            }else if(this.count < node.count){
                return -1;
            }else{
                //比如["2","2","1","1"]的情况 数组中字符串2出现2次 字符串1出现2次 这时候要求按字典顺序输出["1","2"]、["2","2"]1出现2次 2出现2次
                //此时使用原生的比较器 用2个Node对象的string进行字典顺序比较
                //上面的2个条件比较对象是堆顶的元素 被比较对象是要是否加入替代堆顶最小元素的元素 用的是count大小做比较
                //但此时Node值相同,应该比较的是要加入的node的name字典值,小于栈顶元素 才会重新进行构建最小堆 应该反过来比较
                return node.name.compareTo(this.name);
            }
        }
    }
}

发表于 2021-01-21 14:32:17 回复(0)
方法一:先用Map统计str出现次数,然后entrySet用List存储,再自定义排序器用Collections排列;最后取出前k个entry存入结果数组返回。
  • 时间复杂度O(nlogn);
  • 空间复杂度O(n)
import java.util.*;


public class Solution {
    /**
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    public String[][] topKstrings (String[] strings, int k) {
        // write code here
        String[][] ans=new String[k][2];
        if(k==0) return ans;
        
        Map<String,Integer> maps=new HashMap<>();
        for(String str:strings){
            maps.put(str,maps.getOrDefault(str,0)+1);
        }
        
        List<Map.Entry<String,Integer>> list=new ArrayList<Map.Entry<String,Integer>>(maps.entrySet());
        Collections.sort(list,new Comparator<Map.Entry<String,Integer>>(){
            @Override
            public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){
                if(o1.getValue()==o2.getValue()){
                    return o1.getKey().compareTo(o2.getKey());
                }
                return o2.getValue()-o1.getValue();
            }
        });
        
        for(int i=0;i<k;i++){
            ans[i][0]=list.get(i).getKey();
            ans[i][1]=String.valueOf(list.get(i).getValue());
        }
        return ans;
    }
}
方法二:用最小堆。每次把小的元素弹出,最后剩下的k个就是最大的。
  • 时间复杂度:O(nlogk)
  • 空间复杂度:O(n)
import java.util.*;


public class Solution {
    /**
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    public String[][] topKstrings (String[] strings, int k) {
        // write code here
        String [][]ans=new String[k][2];
        if(k==0) return ans;
        
        Map<String,Integer> maps=new HashMap<>();
        for(String str:strings){
            maps.put(str,maps.getOrDefault(str,0)+1);
        }
         PriorityQueue<String> heap=new PriorityQueue<String>(new Comparator<String>(){
             @Override
             public int compare(String s1,String s2){
                 if(maps.get(s1).equals(maps.get(s2))) return s2.compareTo(s1);
                 return maps.get(s1)-maps.get(s2);
             }
         });
        
        for(String str:maps.keySet()){
            heap.offer(str);
            if(heap.size()>k) heap.poll();
        }
//         while(!heap.isEmpty()){
//             System.out.println(heap.poll());
//         }
        for(int i=k-1;i>=0;i--){
            ans[i][0]=heap.poll();
            ans[i][1]=String.valueOf(maps.get(ans[i][0]));
        }
        return ans;
    }
}
注意:比较Integer的大小用equals()!!!!

发表于 2022-05-10 21:38:58 回复(0)
public class Solution {
    /**
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    public String[][] topKstrings (String[] strings, int k) {
        if(k == 0){
            return new String[][]{};
        }
        // 定义hashmap 存储出现的字符串和出现的次数
        Map<String,Integer> map = new HashMap<>();
        for(int i=0;i<strings.length;i++){
            if(map.containsKey(strings[i])){
                map.put(strings[i],map.get(strings[i])+1);
            }else{
                map.put(strings[i],1);
            }
        }
        // 维护K容量的小顶堆;与正常的大顶堆反过来
        Queue<Node> queue = new PriorityQueue<>(k,(Node n1,Node n2)->{
            if(n1.count == n2.count){
                // 如果出现次数相等 则按照字典序从大到小排序(反过来)
                return n2.val.compareTo(n1.val);
            }else{
                // 否则按照出现次数从小到大排序(小顶堆)
                return n1.count-n2.count;
            }
        });
        for(Map.Entry<String,Integer> entry:map.entrySet()){
            if(queue.size()<k){
                queue.add(new Node(entry.getKey(),entry.getValue()));
                continue;
            }
            // 判断当前值和堆顶的值进行比较,如果小则丢掉。如果大则入队。
            Node node = queue.peek();
            if(entry.getValue() < node.count){
                continue;
            }else if(entry.getValue() == node.count){
                if(entry.getKey().compareTo(node.val) < 0){
                    // 堆顶出队
                    queue.poll();
                    queue.add(new Node(entry.getKey(),entry.getValue()));
                }else{
                    continue;
                }
            }else{
                // 堆顶出队
                queue.poll();
                queue.add(new Node(entry.getKey(),entry.getValue()));
            }
        }
        // 队列逐个出队,倒叙输出
        List<String[]> list = new ArrayList<>();
        while(queue.size()>0){
            Node node = queue.poll();
            String[] str = new String[]{node.val,node.count+""};
            list.add(str);
        }
        Collections.reverse(list);
        String[][] res = new String[list.size()][2];
        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }
    class Node{
        String val;
        int count;
        Node(String val,int count){
            this.val = val;
            this.count = count;
        }
    }
}

发表于 2021-05-26 15:58:07 回复(0)
    public String[][] topKstrings (String[] strings, int k) {
        // write code here
        int len = strings.length;
        Map<String,Integer> map = new HashMap<>();
        for (int i=0;i<len;++i){
            map.put(strings[i], map.getOrDefault(strings[i], 0)+1);
        }
        // s[0]:值,s[1]:值出现的次数
        List<String[]> list = new ArrayList<>(map.size());
        for (String key : map.keySet()){
            list.add(new String[]{key, String.valueOf(map.get(key))});
        }
        Collections.sort(list, (s1,s2)->Integer.valueOf(s1[1]) == Integer.valueOf(s2[1]) ? s1[0].compareTo(s2[0]) : Integer.valueOf(s2[1])-Integer.valueOf(s1[1]) );
        String[][] res = new String[k][];
        for (int i=0;i<k;++i){
            res[i] = list.get(i);
        }
        return res;                                                         
    }

发表于 2021-02-01 10:18:51 回复(0)
function topKstrings( strings ,  k ) {
    // write code here
    const map = new Map()
    strings.forEach((item) => {
        if (map.has(item)) map.set(item, map.get(item) + 1)
        else map.set(item, 1)
    })
    return [...map].sort((a, b) => {
        if (a[1] === b[1]) {
            if (a[0] > b[0]) return 1
            else return -1
        } else return b[1] - a[1]
    }).slice(0, k)
}

发表于 2021-11-19 15:38:02 回复(0)
public class ArrayTest {

    // 这个解法应该是初学者最能够理解的吧,全是基础知识,虽然比较消耗资源
    public static List test(String[] arr, Integer k) {
        // 排重计算
        Map<String, Integer> map = new HashMap<>(8);
        for (String key : arr) {
            Integer value = map.get(key);
            if (value == null) {
                map.put(key, 1);
            } else {
                value++;
                map.put(key, value);
            }
        }
        // 将map转成java对象
        List<Node> nodeList = new ArrayList<>();
        Set<String> keySet = map.keySet();
        for (String key : keySet) {
            Node node = new Node();
            node.setKey(key);
            node.setValue(map.get(key));
            nodeList.add(node);
        }
        // 进行排序
        Collections.sort(nodeList);
        // 取前K位的值
        List<Node> nodeList1 = nodeList.subList(0, k);
        // 打印数据
        System.out.println(nodeList1);
        return nodeList1;
    }

}

class Node implements Comparable<Node> {

    private String key;
    private Integer value;

    // 按格式重写toString
    @Override
    public String toString() {
        return "[" + key + "," + value + "]";
    }

    // 先以value排序,再以key做自然排序
    @Override
    public int compareTo(Node o) {
        int num =  o.getValue() - this.getValue();
        return num == 0 ? this.getKey().compareTo(o.getKey()) : num;
    }

    public String getKey() {
        return key;
    }

    public void setKey(String key) {
        this.key = key;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }
}

编辑于 2021-09-18 00:12:24 回复(1)
import java.util.*;

public class Solution {
    public String[][] topKstrings (String[] strings, int k) {
        //统计结果
        Map<String, Integer> map = new HashMap<>();
        for(int i=0; i<strings.length; i++){
            map.put(strings[i], map.getOrDefault(strings[i], 0)+1);
        }
        
        //存入List<Node>方便排序
        List<Node> list = new ArrayList<>();
        Set<String> set = map.keySet();
        for(String key : set){
            list.add(new Node(key, map.get(key)));
        }
        //排序
        Collections.sort(list, new Comparator<Node>(){
            public int compare(Node a, Node b){
                if(a.val!=b.val) return b.val-a.val;
                else return a.s.compareTo(b.s);
            }
        });
        //选最大k个输出
        String[][] res = new String[k][2];
        for(int i=0; i<k; i++){
            res[i][0] = list.get(i).s;
            res[i][1] = String.valueOf(list.get(i).val);
        }
        return res;
    }
}

class Node{
    String s;
    int val;
    public Node(String s, int val){
        this.s = s;
        this.val = val;
    }
}

发表于 2021-09-13 22:05:06 回复(1)
1、先用哈希表记录每个字符串出现的次数
2、再遍历一遍哈希表,遍历过程中用小顶堆存储topk的字符串
3、将小顶堆的数据存储到数组里,由于小顶堆每次弹出的堆顶是次数最小的,所以最后还要逆序一下数组
class Solution {
public:
    /**
     * return topK string
     * @param strings string字符串vector strings
     * @param k int整型 the k
     * @return string字符串vector<vector<>>
     */
    struct cmp {
        bool operator() (pair<int,string> a, pair<int,string> b) {
            return a.first==b.first?a.second<b.second:a.first>b.first;
        }
    };
    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        unordered_map<string,int> fre;
        priority_queue<pair<int,string>,vector<pair<int,string>>, cmp> q; //小顶堆
        unordered_set<string> st;
        for(string& cur:strings) {
            fre[cur]++;
        }
        for(auto iter=fre.begin(); iter!=fre.end(); ++iter) {
            if(q.size()<k) {
                q.push(pair<int,string>{iter->second,iter->first});
            }else if(q.top().first<iter->second || 
                     q.top().first==iter->second && q.top().second>iter->first) {
                q.pop();
                q.push(pair<int,string>{iter->second,iter->first});
            }
        }
        vector<vector<string>> res;
        while(!q.empty()) {
            res.push_back(vector<string>{q.top().second,to_string(q.top().first)});
            q.pop();
        }
        reverse(res.begin(),res.end());
        return res;
    }
};


发表于 2021-09-13 21:46:43 回复(0)
function topKstrings( strings ,  k ) {
    // write code here
    strings.sort();
    let ans = [];
    for(let i = 0 ; i < strings.length;){
        let j = i+1;
        while(j<strings.length&&strings[j]===strings[i]){j++;}
        ans.push([strings[i],(j-i).toString()]);
        i = j;
    }
    ans.sort((a,b)=>b[1]-a[1])
    return ans.slice(0,k);
}

发表于 2021-09-13 13:59:11 回复(0)
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)
nlogk 嘿嘿
import java.util.*;


public class Solution {
    /**
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    
    static class Node {
        String key;
        int cnt;
        Node (String key, int cnt) {
            this.key = key;
            this.cnt = cnt;
        }
    }
    
    public String[][] topKstrings (String[] strings, int k) {
        // write code here
        PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                int r1 = o1.cnt - o2.cnt;
                return r1 == 0 ? o2.key.compareTo(o1.key) : r1;
            }
        });

        HashMap<String, Integer> map = new HashMap<>();
        for (String key : strings) {
            Integer val = map.getOrDefault(key, 0);
            map.put(key, val + 1);
        }

        for (String key : map.keySet()) {
            Integer val = map.get(key);
            if (queue.size() < k) {
                queue.add(new Node(key, val));
            } else {
                Node node = queue.peek();
                if (node.cnt < val) {
                    queue.poll();
                    queue.add(new Node(key, val));
                } else if (val.equals(node.cnt) && node.key.compareTo(key) > 0) {
                    queue.poll();
                    queue.add(new Node(key, val));
                }
            }
        }

        String [][] res = new String[k][2];
        int idx = k - 1;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            res[idx][0] = node.key;
            res[idx][1] = node.cnt + "";
            idx--;
        }

        return res;
    }
}


发表于 2021-08-06 17:25:23 回复(0)
用了 sort 真心木有意思,这里提供一个以空间换时间的方法,目前用时和空间均超过95%的人,并且符合题意要求:
1. 先用字典统计每个字符的词频,同时用 max_count 记录最大词频数
2. 创建一个元素为列表的长度为 max_count + 1 的数组ans,以词频为index,将字符串放到对应的数组中。如果词频相同,那就等于放到了同一index下的数组中。
3. 接下来从最高词频(最大索引)的元素开始,先排序,再根据k的大小按需从ans中抽取满足条件的字符,由于词频即为索引index的值,因此累加即可!
本算法亮点在于用数组的index作为词频,而且获取答案的时候按需索取,k用完之后即可返回答案。
class Solution:
    def topKstrings(self , strings , k):
        res = {}
        result = []
        max_count = 0
        for i in strings:
            res[i] = res.get(i, 0) + 1
            max_count = max(max_count, res[i])
        ans = [[] for _ in range(max_count + 1)]
        for key, value in res.items():
            ans[value].append(key)
        for j in range(max_count + 1):
            if ans[max_count - j] != []:
                ans[max_count - j] = sorted(ans[max_count - j])
                if len(ans[max_count - j]) < k:
                    for ele in ans[max_count - j]:
                        result += [[ele, str(max_count - j)]]
                    k -= len(ans[max_count - j])
                else:
                    for ele in range(k):
                        result += [[ans[max_count - j][ele], str(max_count - j)]]
                    return result


发表于 2021-05-20 23:25:28 回复(1)
function topKstrings( strings ,  k ) {
    // write code here
    strings.sort();
    const map = strings.reduce((pre, cur) => {
        if (pre.has(cur)) pre.set(cur, pre.get(cur) + 1);
        else pre.set(cur, 1);
        return pre;
    }, new Map());
    const res = [];
    map.forEach((val, key) => res.push([key, val]));
    res.sort((a, b) => b[1] - a[1]);
    return res.slice(0, k);
}

发表于 2021-04-22 23:12:06 回复(0)
#include <unordered_map>
class Solution {
public:
    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        vector<vector<string>> ans();
        unordered_map<string, int> m;
        for(string& str:strings) {
            ++m[str];
        }
        if(k==0 || k > m.size()) return ans;
        auto cmp = [] (auto& lh, auto& rh){
            return lh.second > rh.second || (lh.second == rh.second && lh.first < rh.first);
        };
        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> q(cmp);
        for(auto t:m) {
            pair<string, int> temp{t.first, t.second};
            if(static_cast<int>(q.size() )< k)
            q.push(temp);
            else if(!cmp(q.top(), temp)) {
                q.pop();
                q.push(temp);
            }
        }
        while(!q.empty()) {
            ans.emplace_back(vector<string>{q.top().first,to_string(q.top().second)});
            q.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

发表于 2021-01-08 19:31:00 回复(0)
#include<unordered_map>
#include<queue>
struct Cmp{
    //注意堆顶在后面,less是大顶堆,greater是小顶堆
    bool operator() (pair<string,int> &a,pair<string,int> &b){
        //维护一个大小为K的小顶堆才对,小的出去,让大的排在堆顶,true排在后面
        if(a.second != b.second)return a.second > b.second;
        //相同则按照字典序排列
        //字典大的排序
        return a.first < b.first;//字典序小的排在后面
        //return stringCmp(a.first,b.first);
        
    }
};
class Solution {
public:
//     
    /**
     * return topK string
     * @param strings string字符串vector strings
     * @param k int整型 the k
     * @return string字符串vector<vector<>>
     */
    vector<vector<string>> topKstrings(vector<string>& strings, int k) {
        // write code here
        //思路没问题,但是要注意排序处理,字符串比较可以直接使用小于号
        //先统计出频率
        unordered_map<string,int> m;
        for(auto&c : strings){
            m[c]++;
        }
        //优先队列:按照次数的小顶堆,存放最大的n个数
        priority_queue<pair<string,int>,vector<pair<string,int>>,Cmp> q;
        for(auto& c : m){
            if(q.size() < k){
                q.push(c);
            }
            else{
                //判断和堆顶的大小关系 
               q.push(c);
               q.pop();
            }
        }
        k = min(k,(int)m.size());
        vector<vector<string>> ans(k,vector<string>());
        //可以优化一下,直接生成对应大小的数组然后逆序加入就不用reverse了
        while(!q.empty()){
           --k;
            ans[k].push_back(q.top().first);
            ans[k].push_back(to_string(q.top().second));
            q.pop();
        }
        return ans;
    }
};

发表于 2020-11-03 10:56:20 回复(0)
class Solution {
public:
    struct cmp1 {
        bool operator()(pair<string, int> &a, pair<string, int> &b) {
            if (a.second != b.second) return a.second > b.second;
            else return a.first < b.first;
        }
    };
    vector<vector<string>> ans;
    vector<vector<string>> topKstrings(vector<string> &strings, int k) {
        map<string, int> m;
        for (auto &a:strings) m[a]++;
        priority_queue<pair<string, int>, vector<pair<string, int>>, cmp1> p;
        auto ite = m.begin();
        for (int i = 0; i < k; i++,ite++) p.push({ite->first, ite->second});      
        for (; ite != m.end(); ite++) {
            pair<string, int> tmp = p.top();
            if ((ite->second == tmp.second && ite->first < tmp.first) || ite->second > tmp.second) {
                p.pop();
                p.push({ite->first, ite->second});
            }
        }
        ans.resize(k);
        for (int i = k - 1; i >= 0; i--) {
            auto node = p.top();
            p.pop();
            ans[i]={node.first,to_string(node.second)};
        }
        return ans;
    }
};

编辑于 2020-10-21 16:49:31 回复(0)
import java.util.*;

public class Solution {
    /**
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    public String[][] topKstrings (String[] strings, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String string : strings) {
            map.merge(string, 1, Integer::sum);
        }
        Set<String> set = map.keySet();
        List<String> str = new ArrayList<>(set);
        str.sort((s1, s2) -> map.get(s1).equals(map.get(s2)) ? s1.compareTo(s2) : map.get(s2) - map.get(s1));
        String[][] result = new String[k][2];
        for (int i = 0; i < k; i++) {
            result[i] = new String[]{str.get(i), String.valueOf(map.get(str.get(i)))};
        }
        return result;
    }
}


发表于 2021-04-12 22:30:21 回复(1)