算法字符串出现次数的TopK问题

野性酷女 2023-02-08 12:44 35阅读 0赞

import java.util.*;
    
    /**
     * 字符串出现次数的TopK问题
     */
    public class TopKStrings {
        
        /**
         * 给定一个字符串数组，再给定整数k，请返回出现次数前k名的字符串和对应的次数
         * 返回的答案应该按字符串出现频率由高到低排序
         * 如果不同的字符串有相同出现频率，按字典序排序
         * 对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系
         * 比如"ah1x"小于"ahb"，"231"<”32“
         * 字符仅包含数字和字母
         * <p>
         * 如果字符串数组长度为N，时间复杂度请达到O(N \log K)O(NlogK)
         */
        public static String[][] getTopKStrings(String[] strings, int k) {
        
            Map<String, Integer> map = new HashMap<>();
            for (String string : strings) {
        
                if (map.containsKey(string)) {
        
                    map.put(string, map.get(string) + 1);
                } else {
        
                    map.put(string, 1);
                }
            }
            String[][] res = new String[k][2];
            if (map.isEmpty()) {
        
                return res;
            }
            List<Map.Entry<String, Integer>> resList = new ArrayList<>(map.entrySet());
            // 双健排序 1.先根据value的降序 2.后根据key的升序
            resList.sort((entry1, entry2) -> entry2.getValue().compareTo(entry1.getValue()) == 0 ? entry1.getKey().compareTo(entry2.getKey()) : entry2.getValue().compareTo(entry1.getValue()));
            int resI = 0;
            for (Map.Entry<String, Integer> entry : resList) {
        
                if (resI >= k) {
        
                    break;
                }
                res[resI][0] = entry.getKey();
                res[resI][1] = String.valueOf(entry.getValue());
                resI++;
            }
            return res;
        }
    
        public static void main(String[] args) {
        
            String[] str = {
        "a", "b", "c", "b"};
            int k = 2;
            System.out.println(Arrays.deepToString(getTopKStrings(str, k)));
        }
    }