时间戳

首页 > 解决方案 > 这个递归函数是二次时间复杂度吗？

javascript - 这个递归函数是二次时间复杂度吗？

问题描述

以下代码的目的是获取连续重复的字符并移动它们，使它们不再重复。即：'aaabbcc' -> 'abcacba' 如果不可能，则返回 None。

    function sortEvo(str, result) {
        result = result || []

        str = str.split('').sort()

        if (str.length === 0)
            return result.join('')

        const arrLen = str.length - 1
        const resLen = result.length - 1

        if (str[arrLen] !== result[resLen]) 
            result.push(str.pop())
        else if (str[arrLen] !== result[0])
            result.unshift(str.pop())
        else if (str[0] !== result[resLen])
            result.push(str.shift())
        else return 'None'

        return sortEvo(str.join(''), result) 
    }

乍一看，它看起来是线性时间，但我不确定，因为 shift() 和 unshift() 使它遍历数组以重新索引元素。

标签： javascriptalgorithmdata-structures

解决方案

对于线性时间复杂度，您可以indices为数组数组保留一个对象。

在循环中检查字符是否存在于 中indices，如果不存在，则创建一个或增加目标数组的索引。然后将此字符添加到目标数组中。

最后返回扁平并连接的数组。

function maxDistance(string) {
    var indices = {},
        parts = [];
    
    for (const c of string) {
        if (c in indices) indices[c]++;
        else indices[c] = 0;
        
        let i = indices[c];
        if (!parts[i]) parts[i] = [];
        parts[i].push(c);
    }
    return parts.flat().join('');
}

console.log(maxDistance('aaabbcc'));

推荐阅读