解法1

把每个字母出现的频次放到map中,进行暴力排序

public String frequencySort(String s) {

	Map<Character,Integer>map = new HashMap<>();
	StringBuilder stringBuilder = new StringBuilder();
	for (int i = 0; i < s.length(); i++) {
	    map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
	}
	while (map.size()>0){
	    int count = 0;
	    char c = ' ';
	    for (Character character : map.keySet()) {
		if (map.get(character)>count) {
		    count = map.get(character);
		    c = character;
		}
	    }
	    for (int i = 0; i < count; i++) {
		stringBuilder.append(c);
	    }
	    map.remove(c);
	}
	return stringBuilder.toString();

    }

解法2

把每个字母出现的频次放到map中,根据map的结果生成Letter实体,然后放入重写了排序规则的优先队列中,最后依次从优先队列中取出元素。

public String frequencySort2(String s) {

	PriorityQueue<Letter>priorityQueue = new PriorityQueue<>((o1, o2) -> o2.freq-o1.freq);
	Map<Character,Integer>map = new HashMap<>();
	StringBuilder stringBuilder = new StringBuilder();
	for (int i = 0; i < s.length(); i++) {
	    map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
	}
	for (Character character : map.keySet()) {
	    priorityQueue.add(new Letter(character,map.get(character)));
	}
	while (priorityQueue.size()>0){
	    Letter letter = priorityQueue.remove();
	    for (int i = 0; i < letter.freq; i++) {
		stringBuilder.append(letter.letter);
	    }
	}
	return stringBuilder.toString();
    }

    private class Letter{
        private char letter;
        private int freq;

	private Letter(char letter, int freq) {
	    this.letter = letter;
	    this.freq = freq;
	}
    }

意外的是,使用优先队列的效果不如暴力解法, 猜想可能的原因是优先队列的排序上浪费了大量的时间.

解法3

使用桶排序

//使用桶排序
    @SuppressWarnings("unchecked")
    public String frequencySort4(String s){

	Map<Character,Integer>map = new HashMap<>();
	StringBuilder stringBuilder = new StringBuilder();
	ArrayList<Character>[] lists = new ArrayList[s.length()+1];
	for (int i = 0; i < s.length(); i++) {
	    map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
	}
	for (Character character : map.keySet()) {
	    int value = map.get(character);
	    if (lists[value]==null){
	        lists[value] = new ArrayList();
	    }
	    lists[value].add(character);
	}
	for (int i = lists.length-1 ; i>0 ; i--){
	    if (lists[i]==null){
	        continue;
	    }
	    for (Character character : lists[i]) {
		for (int j = 0 ; j<i; j++){
		    stringBuilder.append(character);
		}
	    }
	}
	return stringBuilder.toString();
    }

经检验,桶排序与暴力法的性能最好

最后

以上就是负责高跟鞋为你收集整理的Leetcode451:根据字符出现频率排序解法1解法2解法3的全部内容，希望文章能够帮你解决Leetcode451:根据字符出现频率排序解法1解法2解法3所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。