8ms Java Solution beats 99.61%, ASCII with O(n) time


  • 0
    J

    As always, using ASCII is fast...

    I know the sorting method I used here is ugly : D , (kinda lost patience...), but still, the time complexity on sorting is constant. I think this could be considered as O(n) time solution...

    Code:

    public class Solution {

    public String frequencySort(String s) {
        if (s.length() == 0 || s.length() == 1) return s;
        int[] list = new int[128];
        char[] rst = s.toCharArray();
        for (char c : rst) {
            list[c] = list[c] + 1;
        }
        char[] tmp = new char[128];
        int[] list_tmp = Arrays.copyOf(list, 128);
    
        for (int i = 0; i <= 127; i++) {
            int max = 0;
            int index = 0;
            for (int j = 0; j <= 127; j++) {
                if (max < list_tmp[j]) {
                    max = list_tmp[j];
                    index = j;
                }
            }
            list_tmp[index] = 0;
            tmp[i] = (char)index;
        }
        
        int k = 0;
        for (char c : tmp) {
            for (int j = 0; j < list[c]; j++) {
                rst[k] = c;
                k++;
            }
        }
        list = null;
        list_tmp = null;
        tmp = null;
        
        return String.valueOf(rst);
    }
    

    }


Log in to reply
 

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