451. Sort Characters By Frequency

Posted on | In
Words count in article: 362 | Reading time ≈ 2

题目

Given a string, sort it in decreasing order based on the frequency of characters.

示例1:

1
2
3
4
5
6
7
8
9
Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

示例2：

1
2
3
4
5
6
7
8
9
Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

示例3：

1
2
3
4
5
6
7
8
9
Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

提示:

  1. You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  2. Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

解法

解法一：

构造一个大顶堆，遍历取完即可。

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Node {
		private char c;
		private int times;
		
		public Node(char c, int times) {
			this.c = c;
			this.times = times;
		}

		public char getC() {
			return c;
		}

		public void setC(char c) {
			this.c = c;
		}

		public int getTimes() {
			return times;
		}

		public void setTimes(int times) {
			this.times = times;
		}
	}
	 public String frequencySort(String s) {
		 int[] chars = new int[256];
		 for (char c : s.toCharArray()) {
			 chars[c]++;
		 }
		 
		 PriorityQueue<Node> charNodes = new PriorityQueue<>((a, b) -> b.getTimes() - a.getTimes());
		 for (int i = 0;i < 256;i++) {
			 if (chars[i] == 0) {
				 continue;
			 }
			 
			 Node node = new Node((char) i, chars[i]);
			 charNodes.add(node);
		 }
		 
		 StringBuilder sb = new StringBuilder();
		 while (!charNodes.isEmpty()) {
			 Node node = charNodes.poll();
			 int total = node.getTimes();
			 while (total > 0) {
				 sb.append(node.getC());
				 total--;
			 }
		 }
		 return sb.toString();
	 }
0%