[LeetCode] Sort Characters By Frequency(Java)

92 阅读 0 评论 61 点赞

我是靠谱客的博主朴素书本，最近开发中收集的这篇文章主要介绍[LeetCode] Sort Characters By Frequency(Java)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

我的思想是list数组按顺序构造，讨论中高票使用数组实现，效果更好

我的代码

public class Solution {
    public String frequencySort(String s) {
        int length = s.length();
        List<String>[] sortList = new LinkedList[length+1];
        Map<String,Integer> hash = new LinkedHashMap<String,Integer>();
        StringBuffer result = new StringBuffer();
        for(int i = 0;i < length;i++){
            String key = "" + s.charAt(i);
            hash.put(key,hash.getOrDefault(key, 0) + 1);
        }
        for(Map.Entry<String, Integer> entry : hash.entrySet()){
            int value =  entry.getValue();
            if (sortList[value] == null) {  
                sortList[value] = new LinkedList<String>();  
            } 
            sortList[value].add(entry.getKey());
        }
        for(int i = length;i > 0;i--){
            if(sortList[i] == null)
                continue;
            int len = sortList[i].size();
            for(int j = 0; j < len;j++){
                String val = sortList[i].get(j);
                //System.out.println(val);
                for(int k = 0; k < i;k++){
                    result.append(val);
                }
            }
        }
        //System.out.println(result);
        return result.toString();
    }
}

这个是高票代码

public String frequencySort(String s) {
        if(s.length() < 3)
            return s;
        int max = 0;
        int[] map = new int[256];
        for(char ch : s.toCharArray()) {
            map[ch]++;
            max = Math.max(max,map[ch]);
        }
        String[] buckets = new String[max + 1]; // create max buckets
        for(int i = 0 ; i < 256; i++) { // join chars in the same bucket
            String str = buckets[map[i]];
            if(map[i] > 0)
                buckets[map[i]] = (str == null) ? "" + (char)i : (str + (char) i);
        }
        StringBuilder strb = new StringBuilder();
        for(int i = max; i >= 0; i--) { // create string for each bucket.
            if(buckets[i] != null)
                for(char ch : buckets[i].toCharArray())
                    for(int j = 0; j < i; j++)
                        strb.append(ch);
        }
        return strb.toString();
    }

2016/12/26