-
Notifications
You must be signed in to change notification settings - Fork 1
/
SortCharactersByFrequency.java
74 lines (60 loc) · 2.09 KB
/
SortCharactersByFrequency.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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
package com.leetcode;
import java.util.HashMap;
import java.util.PriorityQueue;
public class SortCharactersByFrequency {
//https://leetcode.com/problems/sort-characters-by-frequency/
class Solution {
public String frequencySort(String s) {
HashMap<Character,Integer> charCount = new HashMap<>();
for(int i = 0 ; i < s.length(); i++){
char ch = s.charAt(i);
charCount.put(ch,charCount.getOrDefault(ch,0)+1);
}
PriorityQueue<Character> maxHeap = new PriorityQueue<>((a,b) -> (charCount.get(b) - charCount.get(a)));
for(char ch : charCount.keySet()){
maxHeap.offer(ch);
}
String result = "";
while(maxHeap.size() > 0){
char ch = maxHeap.poll();
int count = charCount.get(ch);
for(int i = 0 ; i < count ; i++){
result = result + ch;
}
}
return result;
}
}
class SolutionMoreMemory {
public String frequencySort(String s) {
HashMap<Character,Integer> charCount = new HashMap<>();
for(int i = 0 ; i < s.length(); i++){
char ch = s.charAt(i);
charCount.put(ch,charCount.getOrDefault(ch,0)+1);
}
PriorityQueue<Node> maxHeap = new PriorityQueue<>((a, b) -> (b.count - a.count));
for(char ch : charCount.keySet()){
Node node = new Node(ch , charCount.get(ch));
maxHeap.offer(node);
}
String result = "";
while(maxHeap.size() > 0){
Node node = maxHeap.poll();
char ch = node.ch;
int count = node.count;
for(int i = 0 ; i < count ; i++){
result = result + ch;
}
}
return result;
}
}
class Node{
char ch;
int count;
public Node(char ch , int count){
this.ch = ch;
this.count = count;
}
}
}