JavaScript 说一个排序算法
依旧还是面试题,比较麻烦的是,这个排序的关键在于,我们需要时间复杂度为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
评论 (0)