beat 79%, map reduce


  • 0
    W

    我通常很早睡,今天竟然迷迷糊糊地像在梦游一样给做成AC了。太神奇了,记录一下。

        public List<String> topKFrequent(String[] words, int k) {
            int max = 0;
            HashMap<String, Integer> w2c = new HashMap<>();
            for(String str : words) {
                w2c.put(str, w2c.getOrDefault(str, 0) + 1);
                max = Math.max(max, w2c.get(str));
            }
            List<List<String>> bucket = new ArrayList<>();
            for(int i = 0; i <= max; i++) {
                bucket.add(new ArrayList<>());
            }
            
            for(String s : w2c.keySet()) {
                int count = w2c.get(s);
                List<String> strs = bucket.get(count);
                strs.add(s);
                bucket.set(count, strs);
            }
            
            List<String> ret = new ArrayList<>();
            int j = 0;
            for(int i = max; i > 0; i--) {
                List<String> tmp = bucket.get(i);
                if(tmp != null) {
                    int size = tmp.size();
                    Collections.sort(tmp);
                    for(String v:tmp) {
                        if(k-- > 0) ret.add(v);
                        else return ret;
                    }
                }
            }
            return ret;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.