优先级队列
解题思路
先遍历数组并统计每个元素出现的次数，利用 hash 得到 k 个不重复元素；
遍历 hash 中的元素，依次放入长度为 k 的大顶堆；
遍历完成后，大顶堆依次弹出元素，弹出的字符顺序就是要求出的 字符出现频率 的降序排序
复杂度
-
时间复杂度：
O(n+klogk)，其中 n 是字符串的长度，k 是字符串包含的不同字符的个数；- 遍历字符串统计每个字符出现的频率需要
O(n) - 将字符按照出现频率排序需要
O(klogk) - 生成排序后的字符串，需要遍历 k 个不同字符，需要
O(k)，拼接字符串需要O(n)；
- 遍历字符串统计每个字符出现的频率需要
-
空间复杂度：
O(n+k)，其中 n 是字符串的长度，k 是字符串包含的不同字符的个数；空间复杂度主要取决于哈希表、列表和生成的排序后的字符串；
代码实现
var frequencySort = function (s) {
// 1. 先遍历数组并统计每个元素出现的次数，利用 hash 得到 k 个不重复元素；
const map = new Map();
for (let i = 0; i < s.length; i++) {
const frequency = (map.get(s[i]) || 0) + 1;
map.set(s[i], frequency);
}
// 2. 遍历 hash 中的元素，依次放入长度为 k 的大顶堆；
let list = [...map];
let maxHeap = new Heap((a, b) => map.get(a) > map.get(b));
list.forEach(([c, frequency]) => {
maxHeap.push(c);
});
// 3. 大顶堆依次弹出元素，弹出的字符顺序就是要求出的 字符出现频率的降序排序
const ret = [];
for (let i = 0; i < map.size; i++) {
const c = maxHeap.pop();
const frequency = map.get(c);
ret.push(c.padEnd(frequency, c));
}
return ret.join('');
};
class Heap {
constructor(compare) {
this.arr = [0]; // 忽略 0 这个索引,方便计算左右节点
this.compare = compare ? compare : (a, b) => a > b; // 默认是大顶堆
}
get size() {
return this.arr.length - 1;
}
// 新增元素
push(item) {
this.arr.push(item);
this.shiftUp(this.arr.length - 1);
}
// 元素上浮，k 是索引
shiftUp(k) {
let { arr, compare, parent } = this;
// 当前元素 > 父元素，则进行交换
while (k > 1 && compare(arr[k], arr[parent(k)])) {
this.swap(parent(k), k);
k = parent(k); // 更新 k 的位置为父元素的位置（交换了位置）
}
}
// 弹出堆顶
pop() {
if (this.arr.length == 1) return null;
this.swap(1, this.arr.length - 1);// 将结尾元素和堆顶元素交换位置
let head = this.arr.pop(); // 删除堆顶
this.sinkDown(1); // 再做下沉操作
return head;
}
// 元素下沉
sinkDown(k) {
let { arr, compare, left, right, size } = this;
while (left(k) <= size) {
// 1. 拿到左右节点的最大值
let child = left(k);
if (right(k) <= size && compare(arr[right(k)], arr[child])) {
child = right(k);
}
// 2. k 满足大顶堆或小顶堆，什么都不做
if (compare(arr[k], arr[child])) {
return;
}
// 3. 交换位置后，继续下沉操作
this.swap(k, child);
k = child; // 更新位置
}
}
// 获取堆顶元素
peek() {
return this.arr[1];
}
// 获取左边元素节点
left(k) {
return k * 2;
}
// 获取右边元素节点
right(k) {
return k * 2 + 1;
}
// 获取父节点
parent(k) {
return Math.floor(k >> 1);
}
// i、j 交换位置
swap(i, j) {
[this.arr[i], this.arr[j]] = [this.arr[j], this.arr[i]];
}
}
桶排序
解题思路
遍历字符串，统计每个字符出现的频率，同时记录最高频率 maxFreq；
创建 maxFreq 个桶，记录每个出现频率的字符；
按照出现频率从大到小的顺序遍历桶，对于每个出现频率，获得对应的字符，然后将每个字符按照出现频率拼接到排序后的字符串；
复杂度
-
时间复杂度：
O(n+k)，其中 n 是字符串的长度，k 是字符串包含的不同字符的个数；- 遍历字符串统计每个字符出现的频率需要
O(n) - 创建桶并将不同字符加入桶需要
O(k) - 生成排序后的字符串，需要
O(k)的时间遍历桶，以及O(n)的时拼接字符串间；
- 遍历字符串统计每个字符出现的频率需要
-
空间复杂度：
O(n+k)，其中 n 是字符串的长度，k 是字符串包含的不同字符的个数；空间复杂度主要取决于桶和生成的排序后的字符串；
代码实现
var frequencySort = function (s) {
// 1. 遍历字符串，并记录所有字符串出现次数，并记录最大次数
const mp = new Map();
let maxFreq = 0;
for (const ch of s) {
const frequency = (mp.get(ch) || 0) + 1;
mp.set(ch, frequency);
maxFreq = Math.max(maxFreq, frequency);
}
// 2. 根据字符出现最大次数，创建 maxFreq 个桶
const buckets = new Array(maxFreq + 1).fill(0).map(() => []);
for (const [ch, num] of mp.entries()) {
buckets[num].push(ch);
}
// 3. 从大到小遍历所有的桶，出现次数从多到少拼接所有的字符
const ret = [];
for (let i = maxFreq; i > 0; i--) {
const bucket = buckets[i];
for (const ch of bucket) {
for (let k = 0; k < i; k++) {
ret.push(ch);
}
}
}
return ret.join('');
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 239. 滑动窗口最大值
上一篇
评论
