Appearance
451. 根据字符出现频率排序
题目描述
给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 *已排序的字符串 *。如果有多个答案，返回其中任何一个。
示例 1:
**输入: **s = "tree" **输出: **"eert" **解释: **'e'出现两次，'r'和't'都只出现一次。 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2:
**输入: **s = "cccaaa" **输出: **"cccaaa" **解释: **'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。 注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:
**输入: **s = "Aabb" **输出: **"bbAa" **解释: **此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。 注意'A'和'a'被认为是两种不同的字符。
提示:
1 <= s.length <= 5 * 105
- `s` 由大小写英文字母和数字组成
难度： Medium
题解代码
javascript
/**
* @param {string} s
* @return {string}
*/
var frequencySort = function(s) {
};
class Heap {
constructor (data) {
this.data = data
}
sort () {
let iArr = this.data
let n = iArr.length
if (n <= 1) {
return iArr
} else {
// 从最后一个父节点开始依次构建最大堆
for (let i = Math.floor(n / 2); i >= 0; i--) {
Heap.maxHeapify(iArr, i, n)
}
for (let j = 0; j < n; j++) {
Heap.swap(iArr, 0, n - 1 - j)
Heap.maxHeapify(iArr, 0, n - 1 - j - 1)
}
}
return iArr
}
static swap (arr, a, b) {
if (a === b) {
return
}
let temp = arr[b]
arr[b] = arr[a]
arr[a] = temp
}
static maxHeapify (arr, i, size) {
// 左节点索引
let l = 2 * i + 1
let r = 2 * i + 2
let largest = i
if (l <= size && arr[l] > arr[largest]) {
largest = l
}
if (r <= size && arr[r] > arr[largest]) {
largest = r
}
if (largest !== i) {
Heap.swap(arr, i, largest)
Heap.maxHeapify(arr, largest, size)
}
}
}
console.log(new Heap([1,3,6,262,23,55]).sort())