字符串出现次数的TopK问题

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);
            }
        }
    }
}

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;
        }
    }
}

    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;                                                         
    }

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)
}

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;
    }
}

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;
    }
}

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);
}

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);
}

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);
}

#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;
    }
};

#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;
    }
};

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;
    }
};

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;
    }
}

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\
        
        map<string, int> tmp;
        for(int i = 0; i < strings.size(); i++){
            tmp[strings[i]]++;
        }
        vector<vector<string>> res;
        while(k--){
            int num = 0;
            vector<string> vec;
            for(auto it = tmp.begin(); it != tmp.end(); it++){
                num = max(num, it->second);
            }
            for(auto it = tmp.begin(); it != tmp.end(); it++){
                if(it->second == num){
                    vec.push_back(it->first);
                    vec.push_back(to_string(num));
                    tmp.erase(it);
                    break;
                }
            }
            res.push_back(vec);
        }
        return res;
    }
};