CodeSky 代码之空

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

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

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

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

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

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

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

1var sort = function(arr) {
2    var counter = new Array(27),
3        index = 0,      // 计数数组的索引值
4        startAscii = 'a'.charCodeAt(0),
5        arrIndex = 0;   // 代排序数组的索引值
6
7    // 首先,统计出现频率
8    arr.forEach(function(elem) {
9        index = (elem == '*') ? 0 : elem.charCodeAt(0) - startAscii + 1;
10
11        if (isNaN(counter[index])) {
12            counter[index] = 1;
13        } else {
14            counter[index]++;
15        }
16    });
17
18
19    index = 0;
20
21    // 然后,将统计完毕的值依次注入原数组,这样就能保证O1了
22    while (index < 26) {
23        if (!counter[index] || counter[index] == 0) {
24            index++;
25            continue;
26        }
27
28        counter[index]--;
29        if (index == 0) {
30            arr[arrIndex++] = '*';
31        } else {
32            arr[arrIndex++] = String.fromCharCode(index + startAscii - 1);
33        }
34
35    }
36
37    return arr;
38};
39