JavaScript 确定一个字符串的所有字符均不同
上次去Google Girls送了我一本面试金典，前天无聊就看了起来，看到的部分目前还是比较基础也有些意思的，在我看到第一堆算法题的时候我说了一句，这个题看着有点简单啊……然后秒被打脸，可以说，所有的题都是想简单就简单，想难就难，主要看你考虑了多少。
今天就拿其中一道题来说说上面的观点。
实现一个算法，确定一个字符串的所有字符是否不同，假设不允许使用额外的数据结构，又该如何处理。
看完题目，能想到的基本有四种方法，大致总结一下：
第一种叫做直接查找，就是两层循环挨个找，找到相同就跳出。这里毫无疑问时间复杂度O(n^2)，不太靠谱啊。（JS中直接用indexOf）
第二种，先排完序，基本上语言们自带的sort都是快排，O(log(n))，排完再来个O(n)的循环前一个比后一个就能比出来了。
第三种，哈希表，简单粗暴。（JS中用Object或者Map）
第四种，数组统计。（类似于桶）
上面两种如果用C语言实现都是数组去构建的话只是空间不同，时间都是O(n)就行。
之后我们来考虑一下，既然都用JS了，要不试试Map吧——本来我也是这么想的，但是鉴于这是字符串中的字符，不需要区分1和'1'，似乎没有这个必要。
想完一波，是不是太简单了？不对，当时在没有用到额外数据结构的时候我想到的是第四种，但是很快就想到了问题，一般而言我们统计英文当然可以，但是现在除了英文，可能是别的文字吧，那样范围就从ASCII扩展到了UNICODE，那还玩个什么，但是等等，这是歪果仁写的书，会不会限制就是英文。
苦思不得其解，翻到了答案……发现他果然考虑了这个问题……然后做了个ASCII的范围假设。
1const uniqueOrNot2 = function(str) {
2 const length = str.length;
3 const table = new Array(256);
4 let char = 0;
5
6 if (length > 256) {
7 return false;
8 }
9
10 table.fill(false);
11
12 for (let i = 0; i < length; i++) {
13 char = str.charCodeAt(i);
14 if (!table[char]) {
15 table[char] = true;
16 } else {
17 return false;
18 }
19 }
20
21 return true;
22}
23
这里其实又有另一个优化，这个我最初没有考虑到（最初我还在纠结限制范围），那就是如果你知道编码方式，实际上是可以限制字符串长度的最大值，超过长度根本不需要比较。
之后还有一个前方高能版，就是用位运算，其实和数组是一样的，又节省的空间，而且位运算通常更快：
1const uniqueOrNot3 = function(str) {
2 let checker = 0;
3 let start = '0'.charCodeAt(0);
4 let diff = 0;
5 const length = str.length;
6
7 for (let i = 0; i < length; i++) {
8 diff = str.charCodeAt(i) - start;
9
10 if ((checker & (1 << diff)) > 0) {
11 return false;
12 }
13
14 checker = checker | diff;
15 }
16
17 return true;
18}
19
然后我默默收回了说他们简单的话……
评论 (0)