首页 > 试题广场 >

字符串出现次数的TopK问题

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

热度指数：44257 时间限制：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"]]

备注:

算法知识视频讲解

Java

Liebesleid

import java.util.*;

public class Solution {
    /**
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    public static String[][] topKstrings (String[] strings, int k) {
        // write code here
        HashMap<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);
        }
        PriorityQueue<String> heap = new PriorityQueue<String>(k,
        new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return map.get(s1) - map.get(s2);
            }
        });
        for (String s : map.keySet()) {
            if (heap.size() >= k) {
                int top = map.get(heap.peek());
                if (map.get(s) >= top) {
                    heap.poll();
                }
            }
            heap.offer(s);
        }
        String[][] res = new String[2][k];
        while (!heap.isEmpty()) {
            String s = heap.peek();
            int size = heap.size();
            res[size - 1][0] = s;
            res[size - 1][1] = String.valueOf(map.get(s));
            heap.poll();
        }
        return res;
    }
}

发表于 2022-10-08 20:12:56 回复(0)

Java

万顺佑

//第一次写了个超越100%的代码必须记录下
    public String[][] topKstrings(String[] strings, int k) {
        String[][] res = new String[k][2];
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < strings.length; i++) {
            map.put(strings[i], map.getOrDefault(strings[i], 0) + 1);
        }
        PriorityQueue<Map.Entry<String, Integer>> pri = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> map1, Map.Entry<String, Integer> map2) {
                int ans = map2.getValue() - map1.getValue();
                return ans == 0 ? map1.getKey().compareTo(map2.getKey()) : ans;
            }
        });
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            pri.offer(entry);
        }
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> entry = pri.poll();
            res[i][0] = entry.getKey();
            res[i][1] = String.valueOf(entry.getValue());
        }
        return res;
    }

发表于 2022-08-02 17:51:25 回复(0)

Java

圈圈是个圆圆

方法一：先用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)

Java

牛客878205958号

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
//转换Map
Map<String,Integer> countMap = new TreeMap<>();
for(String str:strings){
if(null == countMap.get(str)){
countMap.put(str,1);
}else{
countMap.put(str,countMap.get(str)+1);
}
}
Iterator ite = countMap.entrySet().iterator();
Map<Integer, List<String>> groupMap = new TreeMap<>();
while(ite.hasNext()){
Map.Entry<String,Integer> ele =(Map.Entry<String,Integer>) ite.next();
Integer count = ele.getValue();
if(null ==groupMap.get(count)){
List<String> eleList = new ArrayList<>();
eleList.add(ele.getKey());
groupMap.put(count,eleList);

}else{
List<String> eleList = groupMap.get(count);
eleList.add(ele.getKey());
groupMap.put(count,eleList);
}
}

String[][] result = new String[k][2];
Iterator iteGroup = groupMap.entrySet().iterator();
int cur = 0;
List<Integer> countList = new ArrayList<>();
while(iteGroup.hasNext()){
Map.Entry<Integer,List<String>> ele =(Map.Entry<Integer,List<String>>) iteGroup.next();
countList.add(ele.getKey());
}
Collections.sort(countList);
for(int i=countList.size()-1;i>=0;i--){
Integer key = countList.get(i);
List<String> temp = groupMap.get(key);
for(String str:temp){
if(cur<k){
String[] tep = new String[2];
tep[0] = str;
tep[1] = key+"";
result[cur] = tep;
cur ++;
}else{
break;
}
}
}
return result;

}
}

发表于 2022-04-01 23:05:39 回复(0)

Java

老农爱编程

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
		if (k == 0) {
            String s[][] = new String[0][0];
            return s;
        }
        String[][] res = new String[k][2];
        HashMap<String, Integer> tmap = new HashMap<>();
        for (int i = 0; i < strings.length; i++) {
            String s = strings[i];
            if (!tmap.containsKey(s)) {
                tmap.put(s, 1);
            } else {
                tmap.put(s, tmap.get(s) + 1);
            }
        }
        //将map中的key，value存放到list集合中
        ArrayList<Map.Entry<String, Integer>> list = new ArrayList<>(tmap.entrySet());
        Collections.sort(list,
                         (o1, o2) -> (o1.getValue().compareTo(o2.getValue()) == 0 ? o1.getKey().compareTo(o2.getKey())
                                                                                  : o2.getValue().compareTo(o1.getValue()))
                        );
        for (int i = 0; i < k; i++) {
            res[i][0] = list.get(i).getKey();
            res[i][1] = String.valueOf(list.get(i).getValue());
        }
        return res;
    }
}

发表于 2022-03-15 14:09:14 回复(0)

Java

Jimmy0.0

java 的PriorityQueue好像只能保证权值大小的顺序，但不能保证相同权值的字符的顺序，测试 ["z","y","abcd","abcd","abcd","pwb2","pwb2","pwb2","x"],3 ，输出的却是[["abcd","3"],["pwb2","3"],["x","1"]] ，不符合答案，这里好像是当value的值相同后，比较了key的值来决定出队了，按理由来说还应该比较权值相同时，插入字符在原序列中的顺序优先级。

发表于 2022-03-06 10:41:18 回复(1)

Java

雷欧尼桑

public String[][] topKstrings (String[] strings, int k) {
    Map<String, Integer> map = new HashMap<>();
    for (int i = 0; i < strings.length; i++) {
        if (!map.keySet().contains(strings[i])) {
            map.put(strings[i], 1);
        } else {
            int v = map.get(strings[i]);
            map.put(strings[i], v + 1);
        }
    }
    String[][] strDim = new String[map.size()][2];
    int index = 0;
    for (String key : map.keySet()) {
        strDim[index++] = new String[]{key, String.valueOf(map.get(key))};
    }
    Arrays.sort(strDim, new Comparator<String[]>() {
        public int compare(String[] s1, String[] s2) {
            if (!s1[1].equals(s2[1])) {
                return Integer.parseInt(s2[1]) - Integer.parseInt(s1[1]);
            } else {
                return s1[0].compareTo(s2[0]);
            }
        }
    });
    return Arrays.copyOfRange(strDim, 0, k);
}

发表于 2022-01-04 12:31:40 回复(0)

Java

玄鉴

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
        if(strings.length==0) return new String[0][0];
      HashMap<String,Integer>map=new HashMap<>();
      for(String s:strings){
          map.put(s,map.getOrDefault(s,0)+1);
      }
      PriorityQueue<String[]>queue=new PriorityQueue<>((a,b)->{
          int v1=Integer.parseInt(a[1]);
          int v2=Integer.parseInt(b[1]);
           if(v1!=v2) return v1-v2;
            else return b[0].compareTo(a[0]);

      });
      for(Map.Entry<String,Integer>entry:map.entrySet()){
          String key=entry.getKey();
          String value=entry.getValue()+"";
          String[]arr=new String[]{key,value};
          queue.offer(arr);
          if(queue.size()>k){
             queue.poll();
          }
      }
        String[][]res=new String[k][2];
        int index=k-1;
      while(!queue.isEmpty()){
          res[index--]=queue.poll();
      }  
        return res;
    }
}

发表于 2021-12-21 12:48:32 回复(0)

Java

Carmen-Xiao

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
        if (k == 0)return new String[][]{};
        
        String[][] res = new String[k][2];
        
        Map<String,Integer> map=new HashMap<>();
        
//         TreeMap<String,Integer> map = new TreeMap<>();
        
        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);
            }
        }
        
        ArrayList<Map.Entry<String, Integer>> list =new ArrayList<>(map.entrySet());
        Collections.sort(list,(o1, o2) ->(o1.getValue().compareTo(o2.getValue()) ==0 ? o1.getKey().compareTo(o2.getKey()) :o2.getValue().compareTo(o1.getValue())));
        for (int i = 0; i < k; i++) {
            res[i][0] = list.get(i).getKey();
            res[i][1] = String.valueOf(list.get(i).getValue());
       }
       return res;
    }
}

发表于 2021-11-28 09:59:01 回复(0)

Java

刻苦的大熊猫在度假

java

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
        Map<String, Integer> map = new HashMap<String, Integer>();
        // 统计单词出现的频率
        for(String word : strings){
            map.put(word,map.getOrDefault(word,0)+1);
        }
        // 利用list对map进行按值排序
        List<Map.Entry<String, Integer>> listMap = new ArrayList<>();
        listMap.addAll(map.entrySet());
        Collections.sort(listMap,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 o2.getValue()-o1.getValue();
                }else{  // 出现次数相同，按照单词的字典序排序
                    return o1.getKey().compareTo(o2.getKey());
                }
            }
        });
        // 从map中取出前k个
        String[][] ans = new String[k][2];
        int count = 0;
        for(Map.Entry<String, Integer> lm : listMap){
            if(count == k) break;
            String[] temp = new String[2];
            temp[0] = lm.getKey();
            temp[1] = lm.getValue()+"";
            ans[count] = temp;
            count++;
            
        }
        return ans;
    }
}

发表于 2021-10-08 14:50:15 回复(0)

Java

jackenLeu

// 优先队列节约时间
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][11];
        PriorityQueue<Map.Entry<String,Integer>> q = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(!o1.getValue().equals(o2.getValue())){
                    return o2.getValue()-o1.getValue();
                }
                return o1.getKey().compareTo(o2.getKey());
            }
        });
        Map<String,Integer> mp = new HashMap<>();
        for (String string : strings) {
            mp.put(string,mp.getOrDefault(string,0)+1);
        }
        for(Map.Entry<String,Integer> entry:mp.entrySet()) {
            q.add(new AbstractMap.SimpleEntry<>(entry.getKey(), entry.getValue()));
        }
        int i = 0;
        while(k!=0){
            Map.Entry<String, Integer> poll = q.poll();
            String[] t = new String[2];
            t[0] = poll.getKey();
            t[1] = poll.getValue().toString();
            ans[i] = t;
            i++;
            k--;
        }
        return ans;
     }
}

发表于 2021-10-02 08:22:53 回复(0)

Java

Haochide

import java.util.*;
public class Solution {
 
    public String[][] topKstrings (String[] strings, int k) {
        // write code here
        String[][] ans=new String[k][2];
        HashMap<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);
            }
        }
        PriorityQueue<String[]> pq=new PriorityQueue<>(k+1,(o1,o2)->
         {if(Integer.parseInt(o1[1])==Integer.parseInt(o2[1])) return o2[0].compareTo(o1[0]); return Integer.parseInt(o1[1])-Integer.parseInt(o2[1]);});
        for(String e:map.keySet()){
            String[] s=new String[]{e,Integer.toString(map.get(e))};
            pq.offer(s);
            if(pq.size()>k){
                pq.poll();
            }
        }
        int j=k-1;
        while(!pq.isEmpty()){
            ans[j]=pq.poll();
            j--;
    }
         //   for(int i=k-1;i>=0;i--){
        //        ans[i]=pq.poll();
       //     }
      
        return ans;
    }
}

发表于 2021-09-21 01:46:44 回复(0)

Java

牛客最小的小白

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)

Java

牛气嘣嘣

定义MapTree可以保持键有序，
定义数组String[][] res = new String[k][2];
加入map，key是字符串数值，value是出现的次数。
将map.entrySet()加入ArrayList链表，自定义collections的sort方法：先是按出现次数进行比较，相同的再按照字符ASCII码降序比较。
最后再返回前list中前k个map的key（字符串数值），value（出现次数）。出现次数是int类型，还需要使用String.valueOf()进行转换。

发表于 2021-09-09 20:08:19 回复(0)

提交观点

问题信息

哈希

难度：

36条回答 632收藏 6552浏览

通过挑战的用户

查看代码

想去杭州的布拉...

2023-02-19 14:42:39
乌拉拉肥肥猪

2022-11-15 18:37:21
超级靠谱的内推

2022-11-03 16:38:27
牛客96021...

2022-09-22 11:58:41
_菜鸟_

2022-09-16 10:52:13

字符串出现次数的TopK问题

输入

输出

说明

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题