1.Set+Array
function uniqueArray( array ){
return Array.from(new Set(array))
}
时间复杂度：O(N)
空间复杂度：O(N),因为需要一个额外的Set与Array的存储空间
2. splice
function uniqueArray(arr){
for(var i=arr.length-1;i>=0;i--){
for(var j=i-1;j>=0;j--){
if(arr[i] == arr[j]){
arr.splice(j,1);
}
}
}
return arr;
}
时间复杂度：O(N^2),双重循环，频繁的内存操作
空间复杂度：O(1),因为不需要额外的存储空间
3. Array
function uniqueArray(arr){
var resArr = [];
for(var i of arr){
if( resArr.indexOf(i) < 0 ){
resArr.push(i);
}
}
return resArr;
}
时间复杂度：O(N^2),双重循环，频繁的内存操作
空间复杂度：O(N),因为不需要额外的存储空间
4. Object + Array
function uniqueArray(arr){
var resObj = {};
for(var i of arr){
if( !resObj[i] ){
resObj[i] = 1;
}
}
return Object.keys(resObj);
}
时间复杂度：O(N),Object[key]是采用hash查找，时间复杂度为O(1)
空间复杂度：O(N)
5. 各种方式比较
//随机生成数算法
function randomData(N) {
var randomArr = [];
for( var i=0; i<N ; i++ ){
var random = Math.ceil(Math.random() * N);
randomArr.push(random);
}
return randomArr;
}
//去重算法函数
function uniqueArray( array ){
return Array.from(new Set(array))
}
//时间计算
function calTime(arrN){
var timeLog = [];
for( var i=0; i< arrN.length ; i++ ){
var tempArr = randomData(arrN[i]);
var startDate = new Date().getTime();
uniqueArray(tempArr);
var endDate = new Date().getTime();
timeLog.push( endDate - startDate ) ;
}
console.log(timeLog);
return timeLog;
}
calTime([100,1000,10000]);
按照100,1000,10000等数量级进行比较
| numLevel | Set + Array | splice | Array | Object + Array |
|---|---|---|---|---|
| 100 | 0 | 0 | 0 | 0 |
| 1000 | 0 | 5 | 3 | 1 |
| 10000 | 1 | 235 | 39 | 3 |
| 100000 | 15 | 23431 | 3648 | 20 |
| 1000000 | 280 | - | - | 228 |
总结
1.使用splice去重，随着数量级增大最耗时间。
2.Object + Array去重在大数量级上面表现最好。
3.Array 操作效果明显好于 splice效果
不足
缺少各种方式的详细数据，无法判断在什么情况下使用哪种去重方式最好，希望能够绘制耗费时间折线图
