1366. Rank Teams by Votes
题目详见:1366. Rank Teams by Votes
解法一
思路
这道题是非常 straightforwad 的题目,只要读懂题意,看懂几个例子代表的 edge case 就可以写出代码。
可以利用一个 HashMap 来记录每个字母的得票情况,统计完成后,将字母依次加入定义好的 PriorityQueue 中。我们需要预先重写 PriorityQueue 的排序方式。
最后将 PriorityQueue 中的字母按序取出拼接成字符串。
代码
class Solution {
public String rankTeams(String[] votes) {
int length = votes[0].length(); // 字母个数
Map<Character, int[]> map = new HashMap<>();
// 对每次投票不同位置的字母依次取出
for (String vote : votes) {
for (int i = 0; i < length; i++) {
char c = vote.charAt(i);
map.putIfAbsent(c, new int[length]);
map.get(c)[i]++; // 对该字母相应位次计数
}
}
PriorityQueue<Character> pq = new PriorityQueue<>(new Comparator<Character>(){
@Override
public int compare(Character a, Character b) {
int[] aRank = map.get(a);
int[] bRank = map.get(b);
for (int i = 0; i < length; i++) {
if (aRank[i] != bRank[i]) {
return bRank[i] - aRank[i]; // 降序排列, 即得票权重高的在顶端
}
}
return a - b; // 如果所有字母得票情况一样, 升序排列, 即按字母顺序排列
}
});
for (Map.Entry<Character, int[]> entry : map.entrySet()) {
pq.offer(entry.getKey());
}
StringBuilder sb = new StringBuilder(); // Generate the result
while (!pq.isEmpty()) {
sb.append(pq.poll());
}
return sb.toString();
}
}
复杂度分析
- 时间复杂度 遍历数组 O(26N), 将数组添加进 PriorityQueue 需要 O(26N*logN) 的时间,所以总时间复杂度 O(NlogN).
- 空间复杂度 最多有26个字母,votes 数组长度为 N,则 map 需要有 O(26N) = O(N) 的空间来储存
本作品采用《CC 协议》,转载必须注明作者和本文链接
思路:
思路差不多,我用 php 写的