《前端算法系列》数组去重

徐小夕 等级 757 0 0

虽然算法在前端开发中很少会得以使用,但是了解常用的算法,熟悉各种算法的性能和优劣,将会让你在前端的道路上走的更远。

前言

文中所有代码位于位于此代码仓库中,大家可以下载代码进行学习、推敲和改进。另,如果觉得这些用心推敲的代码对你有帮助的话,欢迎 star 一下代码仓库,众筹博主的小星星。

另外,本文中使用如下函数对代码进行性能测试:

module.exports = async function getFnRunTime(fn) {
    let startTime = Date.now(), endTime;
    let result = await fn();
    endTime = Date.now();
    console.log(`total time:${endTime-startTime}ms`,
                'test array\'length:' + len, 
                result.length
    );
}

为了衡量性能,我们引入代码时间复杂度的概念,用大写O()来表现算法时间复杂度的记法,我们称之为大O记法。一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法。

1.双重for循环去重

如果有相同的值则跳过,不相同则push进数组

function distinct1(arr = testArr) {
    let result = [],
           len = arr && arr.length;
    for (let i=0; i< len; i++) {
        for (let j=i+1; j< len; j++) {
            if (arr[i] === arr[j]) {
                j = ++i;
            }
        }
        result.push(arr[i])
    }
    return result
}

由于使用了双层for循环,根据代码可知时间复杂度为O(n^2),用测试函数测的19815条数据的去重时间为:7-8ms;

2.利用indexOf和forEach/for循环去重

function distinct2(arr = testArr) {
    let result = [];
    arr.forEach((v, i, array) => {
        array.indexOf(v, i+1) === -1 && result.push(v)
    });
    return result
}

可以看到该方法的代码很简洁,时间复杂度为O(n),但是indexOf会进行额外的性能消耗,测试相同的数据耗时为:4-5ms

3.对象法

通过利用对象建名的唯一性去去重

function distinct3(arr = testArr) {
    let result = [], resultObj = {}, len = arr.length;
    for(let i=0; i< len; i++) {
        let val = arr[i],
           type = typeof val;
        if(!resultObj[val]) {
            result.push(val);
            resultObj[val] = [type];
        } else if(!resultObj[val].indexOf(type) < 0) {
            result.push(val);
            resultObj[val] = [type];
        }
    }
    return result
}

该方法很快,时间复杂度为O(n),但是由于会多创建一个对象,会带来额外的内存开销,尤其是数据量大的情景下,测试相同的数据耗时为:5ms

4.filter去重方法一

利用filter和indexOf来查询

function distinct4(arr = testArr) {
    return arr.filter((v, i, array) => array.indexOf(v, i+1) < 0)
}

该方法也很简洁,测试相同的数据耗时为:4-5ms,关键优化点是利用indexOf的第二个参数去避免不必要的查询。

5.filter去重方法二

和方法4的区别是利用数组的索引的唯一性来去重

function distinct5(arr = testArr) {
    return arr.filter((v, i, array) => array.indexOf(v) === i)
}

该方法同4,但是性能远不如方法4,因为数组每次调用indexOf都会重新查找整个数组,但这是必须要做的操作,否则就不能利用数组索引的唯一性了。耗时:16ms(小伙伴们都惊呆了)

6.利用es6的set方法

function distinct6(arr = testArr) {
    return [...new Set(arr)]
}

此方法耗时1ms,但是局限性很大,针对相同类型的数据很快,但是不同类型的数据去重,将非常慢,这涉及到js相关的底层知识,这里就先不介绍了,后期需要的话可以专门上一篇文章介绍~

好啦,其实数组去重有很多种方法,只有你想不到的,没有实现不了的,如果你有更好更快的方法,欢迎一起交流探讨哦~

收藏
评论区

相关推荐

《前端算法系列》数组去重
虽然算法在前端开发中很少会得以使用,但是了解常用的算法,熟悉各种算法的性能和优劣,将会让你在前端的道路上走的更远。 前言 文中所有代码位于位于此代码仓库中(https://link.zhihu.com/?targethttps%3A//github.com/MrXujiang/dataAndMethods),大家可以下载代码进行学习、推敲和改进。
JAVA数组去重常用方法
package com.zxj.test; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map;
JS 两个对象数组合并并去重
JS两个对象数组合并并去重 <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> </body> </htm
java8 stream 集合去重
/** * * Description: JDK1.8的Stream操作工具类 * @author linan.du * @date 2019年7月18日 * @version 1.0 */ public class StreamUtil { /**
Mysql重复数据去重保留一条数据
#### 创建一张测试表 create table poi ( id bigint(20) NOT NULL AUTO_INCREMENT COMMENT 'id', poi_id bigint(20) NOT NULL COMMENT 'poi_id', PRIMARY KEY (`id`) ); #
2018最新Web前端经典面试试题及答案
javascript: ----------- ###  JavaScript中如何检测一个变量是一个String类型?请写出函数实现 typeof(obj) === "string" typeof obj === "string" obj.constructor === String ### 请用js去除字符串空格? ###
2018最新Web前端经典面试试题及答案
javascript: ----------- ###  JavaScript中如何检测一个变量是一个String类型?请写出函数实现 typeof(obj) === "string" typeof obj === "string" obj.constructor === String ### 请用js去除字符串空格? ###
Cocos Creator 获取当前URL取参数
利用Javascript获取当前页的URL,这个问题起来好像很复杂,如果第一次去想这个问题,很多人估计又在琢磨到底又是哪个神一般的Javascript函数。 其实不是,Javascript获取当前页的URL的函数就是我们经常用来重定向的window.location.href。 比如如下函数:  1. <script>   2. var url=w
ES6中some(),取重复值,去重复值和非重复值
var arr=[ { name:'测试' }, { name:'222' }, { name:'测试' }, { name:'另一个' }, { name:'另一
Golang数组去重
方法一: //这种发放适用于string,int,float等切片,会对切片中的元素进行排序 func SliceRemoveDuplicates(slice []string) []string { sort.Strings(slice) i:= 0 var j int
JavaScript去掉数组中的重复元素
题目:去掉数组\[4,3,"3",3,5,7,5\]中的重复元素,返回\[4,3,"3",5,7\] (function() { 'use strict'; function filter1(arr) { var b = []; arr.forEach(function
List stream 对象 属性去重
单值去重不写了,记录对象去重 随手一个对象: @Data @AllArgsConstructor public class Milk { private Integer key; private String value; } 操作: package com.yus.util;
List去重的五种方法
List去重的五种方法。 **方案一、LinkedHashSet是在一个ArrayList删除重复数据的最佳方法,删除重复数据同时保持添加到其中的数据的顺序。** import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedHashSet;
Stream的去重排序
1.List<Integer>排序 List<Integer> list = new ArrayList<>();list.add(50);list.add(25);list.add(25);list.add(98);list.add(32);List<Integer> collect = list.stream().distinct().sort
sql语句_ 的三种去重方法
本文将介绍用 distict、group by 和 row\_number() over 。 注:这里的去重是指:查询的时候, 不显示重复,并不是删除表中的重复项,关系删除表中重复数据的sql 请参考一下链接: https://www.cnblogs.com/171207xiaohutu/p/11520763.html 1\. distinct 表u