151、根据字符出现频率排序

题目描述:
给定一个字符串,请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:
“tree”

输出:
“eert”

解释:
'e’出现两次,'r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外,"eetr"也是一个有效的答案。
示例 2:

输入:
“cccaaa”

输出:
“cccaaa”

解释:
'c’和’a’都出现三次。此外,"aaaccc"也是有效的答案。
注意"cacaca"是不正确的,因为相同的字母必须放在一起。
示例 3:

输入:
“Aabb”

输出:
“bbAa”

解释:
此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。
注意’A’和’a’被认为是两种不同的字符。

代码:
jdk8之后对map的value之后变得更简单了,比如
151、根据字符出现频率排序
这就实现了对value的升序

import java.util.Map;
import java.util.Map.Entry;
class Solution {
    public String frequencySort(String s) {
        //		按照value进行排序
		Map<Character, Integer> map = new TreeMap();
		for (int i = 0; i < s.length(); i++) {
			char tem = s.charAt(i);
			map.put(tem, map.getOrDefault(tem, 0) + 1);
		}
		List<Map.Entry<Character,Integer>>list = map.entrySet().stream()
			      .sorted((entry1, entry2) -> entry2.getValue().compareTo(entry1.getValue()))
			      .collect(Collectors.toList());
		StringBuilder sb = new StringBuilder();
		for (Entry<Character, Integer> entry : list) {
			int get = entry.getValue();
			char gets = entry.getKey();
			for (int i = 0; i < get; i++) {
				sb.append(gets);
			}
		}
		
		return sb.toString();
    }
}

当然也可以使用优先级队列来

import java.util.Map;
import java.util.Map.Entry;

class Solution {
    public String frequencySort(String s) {
    Map<Character, Integer> map = new TreeMap();
		for (int i = 0; i < s.length(); i++) {
			char tem = s.charAt(i);
			map.put(tem, map.getOrDefault(tem, 0) + 1);
		}
		PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
				(o1,o2) -> o2.getValue() - o1.getValue());
		pq.addAll(map.entrySet());
		int len=pq.size();
		StringBuilder sb = new StringBuilder();
        for(int i=0;i<len;i++){
        	char key=pq.peek().getKey();  //获取堆顶元素的键
        	int value=pq.poll().getValue();//获取并弹出堆顶元素的值
        	while(value-->0)
        		sb.append(key);	
        }       	
        return sb.toString();
    }
}

排名靠前的代码
这个设计的就挺好的

class Solution {
    public String frequencySort(String s) {
        StringBuilder sb = new StringBuilder();
        int[] count = new int[256];
        for (char c : s.toCharArray()) {
            ++count[c];
        }

        int[] clone = count.clone();
        Arrays.sort(count);
        for (int i = count.length - 1; i >= 0; i--) {
            if (count[i] == 0) {
                break;
            }

            for (int j = 0; j < clone.length; j++) {
                if (clone[j] == count[i]) {
                    while (count[i]-- > 0) {
                        sb.append((char) j);
                    }
                    clone[j] = 0;
                }
            }
        }

        return sb.toString();
    }
}
上一篇:Phone List(trie树)


下一篇:TE波TM波和TEM波波阻抗