Gather ye rosebuds while ye may

JS去重


看了一个题,要求用JS给数组去重。
标答的实现时间复杂度比我自己想的版本要多一些,下面记录一下自己的版本。


标答的实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function getDist(a) {  
    var res = [];  
    res[0] = a[0];  
    key = 1;  
    for (i = 1; i < a.length; i++) {  
        flag = false;  
        for (j = 0; j < key; j++) {  
            if (a[i] == res[j]) {  
                flag = true;  
                break;  
            }  
        }
        if (flag === false) {
            res[key] = a[i];  
            key++;  
        }  
    }  
    return res;  
}

简单来说就是两个遍历,第一个遍历是把原数组中的值拿出来,第二个遍历是把值和返回值中的比较,若不相同就放进去。
理解上来还是挺简单的,后来我发现其实不用两次遍历的,里面的遍历其实可以不用for。
话说上面这个的时间复杂度我还真不会算了,貌似是O(n^2),但是中间明显不是n次。
应该是大于O(n),小于O(n^2),难道是O(nlgn)?

我的实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function getDist2(a) {
	var res = [];
	res[0] = a[0];
	for (i = 1; i < a.length; i++) {
		if (res.toString().indexOf(a[i]) === -1) {
			res.push(a[i]);
		}
	}
	return res;
}

一开始就想找index的,结果发现JS里面数组没有这个函数,字符串才有,于是就有了这个版本。
先转换为字符串,再indexOf。
好像也没有append函数,只有push。


以上


抱歉,评论已关闭。
欲参与讨论,请寄 [email protected]