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)