leetcode String Hash Map

leetcode 451题

Posted by franki on January 4, 2021

leetcode 451题 给定一个字符串，请将字符串里的字符按照出现的频率降序排列

示例 1:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:

输入:
"Aabb"

输出:
"bbAa"

解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

思路

用hash表统计字符出现的次数，接着排序，最后遍历输出结果

使用map

代码

function frequencySort(str) {
    const hash = {};

    for (const s of str) {
        if (!hash[s]) {
            hash[s] = 1;
        } else {
            hash[s] += 1;
        }
    }

    const arr = [];
    for (let key in hash) {
        const obj = {val: key, count: hash[key]};
        arr.push(obj);
    }

    arr.sort((a, b) => b.count - a.count);

    let res = "";
    for (let i=0; i<arr.length; i++) {
        for (let j=0; j<arr[i].count; j++) {
            res += arr[i].val;
        }
    }

    return res;
}

var frequencySort = function(s) {
    let map = new Map();

    for (const item of s) {
        map.set(item, map.get(item) ? map.get(item)+1 : 1);
    }

    map = [...map].sort((a, b) => b[1] - a[1]);

    let res = "";
    for (const [key, val] of map) {
        for (let i=0; i<val; i++) {
            res += key;
        }
    }
    return res;
};

复杂度分析

  • 时间复杂度: O(MN)
  • 空间复杂度: O(N)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS