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
| class Solution {
public String reorganizeString(String s) {
int[] charCount = new int[26];
char[] sArray = s.toCharArray();
int max = 0;
char maxChar = '*';
for (int i = 0; i < sArray.length; i++) {
char currChar = sArray[i];
charCount[currChar - 'a'] += 1;
if (charCount[currChar - 'a'] > max) {
max = charCount[currChar - 'a'];
maxChar = currChar;
}
}
if (max > (s.length() + 1) / 2)
return "";
char[] ans = new char[s.length()];
int index = 0;
while (charCount[maxChar - 'a'] > 0) {
ans[index] = maxChar;
charCount[maxChar - 'a'] -= 1;
index += 2;
}
int ptr = 0;
while (ptr < charCount.length) {
while (charCount[ptr] > 0) {
if (index >= s.length()) {
index = 1;
}
ans[index] = (char) ('a' + ptr);
charCount[ptr] -= 1;
index += 2;
}
ptr += 1;
}
return String.valueOf(ans);
}
}
|
有点儿类似task scheduler那道题. 就是出现频率最多的char作为底子, 在它们之间插入其他的char. 我们首先将出现频率最多的char统计一下频率. 如果是偶数, 超过(s.length()) / 2, 那就说明不能构成, 如果是奇数, 那么超过1 + (s.length()) / 2就不行. 那如何不用判断奇偶就能知道是否能构成呢? 就是(s.length() + 1) / 2. 这是个好方法. 我们从0开始填, 间隔1. 等到填写完后, 处在的位置可能还是数组中的某个位置, 之后我们开始填写其他的char. 等到index大于等于s.length()的时候, 偶数位填写完毕, 我们再接着填写奇数位. 这就ok了.
时间复杂度: O(n)
空间复杂度: O(1) 因为就使用了一个长度为26的数组.
