451. Sort Characters By Frequency

Version #2 Bucket Sort
77.15 %

public class Solution {
    public String frequencySort(String s) {
        if (s == null || s.length() <= 1) return s;
        int[] freq = new int[128];
        int maxFreq = 0;
        for (char c : s.toCharArray()) {
            freq[c] += 1;
            maxFreq = Math.max(maxFreq, freq[c]);
        }
        List<List<Character>> bucket = new ArrayList<>();
        while (maxFreq-- >= 0) {
            bucket.add(new ArrayList<Character>());
        }
        int index = 0;
        for (char c = 0; c < 128; c++) {
            bucket.get(freq[c]).add(c);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = bucket.size() - 1; i > 0; i--){
            List<Character> list = bucket.get(i);
            for (Character c : list) {
                for (int count = 0; count < i; count++) {
                    sb.append(c);
                }
            }
        }
        return sb.toString();
    }
}


Version #1 Self defined Cell class

sort O(nlogn)
other operations O(n)
debug了一会儿老是出现outofboundary原来问题是ASCII里面capital letter和smallcase letter不是挨着的！！！所以浪费了一点空间直接用了128
不过也省事了不用再-'a'了

90.98 %



class Cell {
    public char character;
    public int freq;
    public Cell() {
        this.character = 0;
        this.freq = 0;
    }
    public Cell(char character, int freq) {
        this.character = character;
        this.freq = freq;
    }
}

public class Solution {
    public String frequencySort(String s) {
        if (s == null || s.length() <= 1) return s;
        //index-ASCII of character
        //value-char & freq
        Cell[] array = new Cell[128];
        for (int i = 0; i < array.length; i++) {
            array[i] = new Cell();
        }
        int index = 0;
        for (char c : s.toCharArray()) {
            //System.out.println(c);
            if (array[c].character == 0) array[c].character = c;
            array[c].freq += 1;
        }
     
        Arrays.sort(array, new Comparator<Cell>() {
            public int compare(Cell cell1, Cell cell2) {
                if (cell1.freq == cell2.freq) {
                    return cell1.character - cell2.character;
                } else {
                    return cell2.freq - cell1.freq;
                }
            }
        });
        StringBuilder sb = new StringBuilder();
        char currChar;
        for (Cell curr : array) {
            currChar = curr.character;
            if (curr.freq == 0) break;
            for (int i = 0; i < curr.freq; i++) {
                sb.append(currChar);
            }
        }
        return sb.toString();
    }
}