Sắp xếp ký tự theo tần suất JavaScript

Cho một chuỗi, hãy sắp xếp nó theo thứ tự giảm dần dựa trên tần suất xuất hiện của các ký tự

ví dụ 1

Đầu vào. "cây"

đầu ra. "eert"

Giải thích.
'e' xuất hiện hai lần trong khi 'r' và 't' đều xuất hiện một lần.
Vì vậy, 'e' phải xuất hiện trước cả 'r' và 't'. Do đó "eetr" cũng là một câu trả lời hợp lệ.

thuật toán

1. Lưu các tần số trong một hashtable
2. Sắp xếp tần số theo thứ tự giảm dần
3. xây dựng lại chuỗi dựa trên tần số

Cách tiếp cận mảng

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
  let res = "";
  let map = new Array(128).fill(0);
  for (let i = 0; i < s.length; i++) {
    map[s.charCodeAt(i)]++;
    }
    while(res.length !== s.length) {
        let max = Math.max(...map)
        let idx = map.indexOf(max)
        res = res + String.fromCharCode(idx).repeat(max)
        map[idx] = 0
    }
    return res
};

Phương pháp tiếp cận mảng được tối ưu hóa

Ý tưởng là lưu trữ các ký tự dựa trên tần suất trong mảng

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
  let map = new Array(128).fill(0);
  let max = 0;
  for (let i = 0; i < s.length; i++) {
    map[s.charCodeAt(i)]++;
    max = Math.max(max, map[s.charCodeAt(i)]);
  }
  let hash = new Array(max + 1).fill("");
  for (let i = 0; i < 127; i++) {
    let val = map[i];
    hash[max - val] += String.fromCharCode(i).repeat(val);
  }
  return hash.join("");
};

Sử dụng đối tượng

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
    let hashMap = {}
    let res = ""
    for(let i = 0; i < s.length; i++) {
        hashMap[s[i]] = hashMap[s[i]] + 1 || 1
    }
    // sort the characters based on frequency
    let sortedArr = Object.keys(hashMap).sort((a, b) => hashMap[b] - hashMap[a])
    sortedArr.forEach(e => {
        res += e.repeat(hashMap[e])
    })
    return res
};