Bucket Sort, O(n)


  • 1
    S

    Similar solution to Leetcode 347.

    public class Solution {

    public String frequencySort(String str) {
        Map<Character, Integer> map = new HashMap<>();
        char[] charStr = str.toCharArray();
        for(int i = 0; i < charStr.length; i++)
        {
            if(map.containsKey(charStr[i]))
            {
                int frequency = map.get(charStr[i]);
                map.put(charStr[i], frequency + 1);
            }
            else
            {
                map.put(charStr[i], 1);
            }
        }
    
        List<Map.Entry<Character, Integer>>[] bucket = new List[charStr.length + 1];
        for(Map.Entry<Character, Integer> entry : map.entrySet())
        {
            int frequency = entry.getValue();
            if(bucket[frequency] != null)
            {
                bucket[frequency].add(entry);
            }
            else
            {
                bucket[frequency] = new LinkedList<>();
                bucket[frequency].add(entry);
            }
        }
        
        StringBuilder res = new StringBuilder();
        for(int i = charStr.length; i >= 0; i--)
        {
            if(bucket[i] != null)
            {
                for(int j = 0; j < bucket[i].size(); j++)
                {
                    char c = bucket[i].get(j).getKey();
                    for(int k = 0; k < i; k++)
                    {
                        res.append(c);
                    }
                }
            }
        }
        return res.toString();
    }
    

    }


Log in to reply
 

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