验证LeetCode 451字符频率排序JS解法的时间与空间复杂度

我正在准备面试，面试官常会询问时间与空间复杂度，因此想确认我对LeetCode 451题解法的复杂度分析是否正确。

问题描述 #

给定字符串s，根据字符出现频率降序排序，返回排序后的字符串（若有多个答案，返回任意一个即可）。

示例1 #

输入：s = "tree"
输出："eert"
解释：'e'出现2次，'r'和't'各出现1次，'e'需排在前，"eetr"也为有效答案。

示例2 #

输入：s = "cccaaa"
输出："aaaccc"
解释：'c'和'a'均出现3次，"cccaaa"和"aaaccc"均有效，"cacaca"无效（相同字符需连续）。

示例3 #

输入：s = "Aabb"
输出："bbAa"
解释："bbaA"也有效，"Aabb"无效，'A'与'a'视为不同字符。

我的JS解法 #

var frequencySort = function(s) {
    //keep a charDict of the chars and frequency 
    //use Object.entries(charDict) to return a 2D array with char and freq
    //use .sort() to sort by frequency (decrementing)
    //return, via map over the sorted array, char.repeat(freq)  
    
    let charDict = {}
    
    for(let char of s){
        if(charDict[char]){
            charDict[char] ++
        }
        else {
            charDict[char] = 1
        }
    }
    
    const sortedArr = Object.entries(charDict)
                        .sort(([,a],[,b]) => b-a)

    return sortedArr.map(([char, freq]) => char.repeat(freq)).join('')
};

我的复杂度假设 #

时间复杂度为O(n*logn)（因使用了.sort()方法），空间复杂度为O(1)，但不确定空间复杂度的分析是否正确，想得到验证。

复杂度分析验证 #

时间复杂度：你的分析是正确的 #

• 统计字符频率的循环遍历字符串，时间复杂度为O(n)，其中n是输入字符串的长度。
• 将字符频率字典转为数组后，调用sort()方法排序。数组的长度k是字符串中不同字符的数量，排序的时间复杂度为O(k logk)。
• 最坏情况下，字符串中所有字符都不重复（k = n），此时排序的时间复杂度变为O(n logn)，整体时间复杂度由这一步主导，因此最终时间复杂度为O(n logn)。

空间复杂度：你的分析存在需要补充的细节 #

空间复杂度的判断取决于对字符集范围的假设：

1. 固定大小字符集（如ASCII、大小写字母+数字）：
   不同字符的数量k是一个常数（比如ASCII有128个字符），此时charDict和sortedArr占用的空间都是常数级，属于O(1)。这种场景下你的结论成立。
2. 任意字符集（如Unicode包含大量不同字符）：
   最坏情况下，字符串中所有字符都不重复（k = n），此时charDict需要存储n个键值对，sortedArr也需要存储n个元素，额外空间复杂度为O(n)。

另外需要注意：最终生成的结果字符串属于题目要求的输出空间，通常不计入额外空间复杂度的计算。

内容的提问来源于stack exchange，提问作者abzzzz96