C++ O(n) solution, 16ms, using Counting Sort, with simple explanation

  • 0

    We first use a hashmap: freq[256] to calculate frequency for each letter. Then, we sort the freq using Counting Sort. In the definition of counting sort, we must know the range of the input element, that is: 0 ~ maximum frequency, so we must record maximum frequency (K) when calculating frequency for each letter. In addition, we eliminate sorting the freq[i] = 0, because it does not matter.

    string frequencySort(string s) {
            int freq[256];
            for(int i=0; i<256;i++) freq[i]=0;
            int K=0,charCount=0;
            for(iterator *it=s.begin();it!=s.end();it++)
                if(freq[*it]==0) charCount++;
                if(freq[*it]>K) K=freq[*it];
            int *B = new int[charCount];
            int *C = new int[K+1];
            for(int i=0; i<=K; i++) C[i]=0;
            for(int i=0; i<256; i++) C[freq[i]]++;
            for(int i=2; i<=K; i++) C[i]=C[i]+C[i-1];
            for(int i=255; i>=0; i--)
                    B[C[freq[i]]-1] = i;
            string freqS;
            for(int i=charCount-1; i>=0; i--)
                for(int j=0; j<freq[B[i]];j++)
            return freqS;

Log in to reply

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