JavaScript 说一个排序算法

依旧还是面试题,比较麻烦的是,这个排序的关键在于,我们需要时间复杂度为O(n),空间复杂度为O(1)。

题目大概是这样的,看了输入输出基本就会明白了:

input: arr = ['', 'a', 'b', '', 'a', 'c', '*', 'm']
output: [ '', '', '*', 'a', 'a', 'b', 'c', 'm' ]
问题描述:将数组中的字母与星号分开

这里其实主要没做出来是因为我没有很好地理解怎么计算复杂度,尤其是空间复杂度,时间复杂度我勉强记忆成for循环的嵌套还是可以的,但是空间复杂度呢?

这里空间复杂度意味着没有长度为n的数组(但是可以是常量个)。

括号里的当时是我没想到的部分,我以为是:一个数组都不能开。

那么问题也就迎刃而解了,使用类似于桶排序的方法即可:

var sort = function(arr) {
    var counter = new Array(27),
        index = 0,      // 计数数组的索引值
        startAscii = 'a'.charCodeAt(0),
        arrIndex = 0;   // 代排序数组的索引值

    // 首先,统计出现频率
    arr.forEach(function(elem) {
        index = (elem == '*') ? 0 : elem.charCodeAt(0) - startAscii + 1;

        if (isNaN(counter[index])) {
            counter[index] = 1;
        } else {
            counter[index]++;
        }
    });


    index = 0;

    // 然后,将统计完毕的值依次注入原数组,这样就能保证O1了
    while (index < 26) {
        if (!counter[index] || counter[index] == 0) {
            index++;
            continue;
        }

        counter[index]--;
        if (index == 0) {
            arr[arrIndex++] = '*';
        } else {
            arr[arrIndex++] = String.fromCharCode(index + startAscii - 1);
        }

    }

    return arr;
};

如果您觉得文章不错,可以通过赞助支持我

标签: 知识, 代码段, 题目, 算法

添加新评论