Sort Characters By Frequency-K6K4.com

原题： https://leetcode.com/problems/sort-characters-by-frequency/description/

题意： 给定一个字符串，将字符按照出现次数倒序排列

例子：

例一:
输入:"tree"    输出:"eert"
说明:'e' 出现了两次而 'r' 和 't' 都出现了一次.
所以 'e' 必须出现在 'r' 和 't'之前. 因此 "eetr" 也是一个有效的答案.

例二:
输入:"cccaaa"    输出:"cccaaa"
说明: 'c' 和 'a' 都出现了三次, 所以 "aaaccc" 也是一个有效的答案.
注意 "cacaca" 是不正确的, 因为相同的字母必须连在一起.

例三:
输入:"Aabb"   输出:"bbAa"
说明:"bbaA" 也是一个有效的答案, 但是 "Aabb" 是不正确的.
注意 'A' 和 'a' 被看做是两个不同的字母.

标签： cccaaa、bbaa、aabb、frequency、characters、面试

猜你感兴趣的圈子：

LeetCode交流圈

星空

2017-08-18 17:34:07 1楼#1层

class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        return ''.join(c * t for c, t in collections.Counter(s).most_common())

星空

2017-08-18 17:34:36 2楼#1层

public class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> charFreqMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            charFreqMap.put(c, charFreqMap.getOrDefault(c, 0) + 1);
        }
        ArrayList<Map.Entry<Character, Integer>> list = new ArrayList<>(charFreqMap.entrySet());
        list.sort(new Comparator<Map.Entry<Character, Integer>>(){
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        StringBuffer sb = new StringBuffer();
        for (Map.Entry<Character, Integer> e : list) {
            for (int i = 0; i < e.getValue(); i++) {
                sb.append(e.getKey());
            }
        }
        return sb.toString();
    }
}

星空

2017-08-18 17:35:15 3楼#1层

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char,int> freq;
        vector<string> bucket(s.size()+1, "");
        string res;
        
        //count frequency of each character
        for(char c:s) freq[c]++;
        //put character into frequency bucket
        for(auto& it:freq) {
            int n = it.second;
            char c = it.first;
            bucket[n].append(n, c);
        }
        //form descending sorted string
        for(int i=s.size(); i>0; i--) {
            if(!bucket[i].empty())
                res.append(bucket[i]);
        }
        return res;
    }
};

星空

2017-08-18 17:36:40 4楼#1层

public class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        List<Character> [] bucket = new List[s.length() + 1];
        for (char key : map.keySet()) {
            int frequency = map.get(key);
            if (bucket[frequency] == null) {
                bucket[frequency] = new ArrayList<>();
            }
            bucket[frequency].add(key);
        }
        StringBuilder sb = new StringBuilder();
        for (int pos = bucket.length - 1; pos >=0; pos--) {
            if (bucket[pos] != null) {
                for (char num : bucket[pos]) {
                    for (int i = 0; i < map.get(num); i++) {
                        sb.append(num);
                    }
                }
            }
        }
        return sb.toString();
    }
}

取消

回复

推荐圈子

LeetCode交流圈