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
| class Solution {
public int minimumKeypresses(String s) {
int[] charCount = new int[26];
char[] sArray = s.toCharArray();
for (char letter : sArray) {
charCount[letter - 'a'] += 1;
}
PriorityQueue<Integer> charCountPQ = new PriorityQueue<>((a, b) -> b - a);
for (int i = 0; i < 26; i++) {
if (charCount[i] != 0) {
charCountPQ.offer(charCount[i]);
}
}
int count = 0, press = 0, ans = 0;
while (!charCountPQ.isEmpty()) {
if (count % 9 == 0) {
press += 1;
}
int currFreq = charCountPQ.poll();
ans += press * currFreq;
count += 1;
}
return ans;
}
}
|
Greedy. 就是让出现频率最多的去占有每一个button的第一个位置. 因此从大到小排列, 分别去占每个button的第一个位置, 占满后占用第二个位置, 以此类推.
时间复杂度: O(N + 26log26 + 26) = O(N). 得到每个char的freq是O(n), 给PQ则最多26个元素, 因此是O(26log26). 把PQ的元素都poll出来, 一共最多26个. 因此合在一起是O(N).
空间复杂度: O(26 + 26) = O(1). 存freq是长度为26的数组. PQ最多存26个元素.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int minimumKeypresses(String s) {
Integer[] charCount = new Integer[26];
Arrays.fill(charCount, 0);
char[] sArray = s.toCharArray();
for (char letter : sArray) {
charCount[letter - 'a'] += 1;
}
Arrays.sort(charCount, (a, b) -> b - a);
int ans = 0;
for (int i = 0; i < 26; i++) {
ans += charCount[i] * ((i + 9) / 9);
}
return ans;
}
}
|
上面傻了, 我们只需要用个array存一下每一个char的freq即可. 由于普通int array无法倒序sort, 因此我们用个Integer[].
时间复杂度和空间复杂度不变.
