leetcode

leetcode 451题

Posted by franki on October 21, 2022

leetcode 451 根据字符出现频率排序

给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。

返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

示例1

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

示例2

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

示例3

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

提示：

  • 1 <= s.length <= 5 * 105
  • s 由大小写英文字母和数字组成

思路

先统计字符串中每个字符出现的次数，然后进行排序，最后进行打印输出

代码

/**
 * @param {string} s
 * @return {string}
 */
function frequencySort(s) {
    const freq = {};

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

    return Object.entries(freq).sort((a, b) => b[1] - a[1]).map(([key, value]) => key.repeat(value)).join('');
}

复杂度分析:

  • 时间复杂度: O(N)
  • 空间复杂度：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