Java Easy to understand O(n logn), beats 90%


  • 4
    A
    public class Solution {
        
        class Entry{
            char c;
            int count;
            
            public Entry(){
                this.count = 0;
            }
        }
        
        public String frequencySort(String s) {
            
            Entry[] elems = new Entry[256];
            for(int i=0; i<256; i++){
                elems[i] = new Entry();
            }
            
            for(int i=0; i<s.length(); i++){
                char c = s.charAt(i);
                elems[c].c = c;
                elems[c].count++;
            }
    
            Arrays.sort(elems, new Comparator<Entry>(){
               @Override
               public int compare(Entry e1, Entry e2){
                   return e2.count - e1.count; // descending order
               }
            });
            
            StringBuilder result = new StringBuilder();
            for(Entry e: elems){
                while(e.count-- > 0)
                    result.append(e.c);
            }
            
            return result.toString();
            
        }
    }
    
    

  • 1
    A

    I think the time complexity of your solution is actually O(n).
    The most time consuming part:
    for(int i=0; i<s.length(); i++){
    ...
    }
    Since the Entry[] contains fixed 256 element, you can treat the sorting cost over it as constant, which is O(1).


  • 0
    C

    I got almost the same solution, but avoiding using new class, a 2-d array is enough. By the way it should be O(n) as @airwindow has pointed out. I think this solution is cleaner than most other solutions using maps.

    public String frequencySort(String s) {
            
            int[][] stat = new int[256][2];
            
            for(int i = 0; i < 256; i++) {
                stat[i][0] = i;
            }
            
            for(char c : s.toCharArray()) {
                stat[(int) c][1]++;
            }
            
            Arrays.sort(stat, new Comparator<int[]>() {
               public int compare(int[] a, int[] b) {
                   return b[1] - a[1];
               } 
            });
            
            StringBuffer res = new StringBuffer();
            
            for(int i = 0; stat[i][1] > 0; i++) {
                for(int j = 0; j < stat[i][1]; j++) {
                    res.append((char)stat[i][0]);
                }
            }
            
            return res.toString();
            
        }
    

Log in to reply
 

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