专栏首页原创如何用JavaScript进行数组去重

如何用JavaScript进行数组去重

今天的文章和大家谈一谈如何用JavaScript进行数组去重,这是一道常见的面试(笔试)题,可以很好地考察出一个人的逻辑思维及边界考虑情况,希望此文能够帮助大家在解决类似问题时拓宽思路。据我到目前为止面试的情况,很少有人能在现场考虑很全,基本上的人都是浅尝辄止。

当然,“使用库中的一个函数就能去重”并不在本篇文章的讨论范围内,我们针对的是需要自己写代码的场景。考虑到实际情况,我们使用ES5(主要就用了indexOf方法,如果是更古老的环境,可以自己增加这段代码,或者使用ES5兼容库es5-sham.js)。

我们先审题:数组,题目中并没有说是什么样的数组,即数组的组成元素可能是字符串、数字、布尔、数组、对象、Null、Undefined。

在开始之前我们先看看这些类型以及他们的值比较关系:

接着我们来看看数组中的indexOf方法:

var gtArray = [66],
gtObject = {
id: 1
},
gtTestArr = ["1", 1, true, [66],
gtArray, { id: 1 }, gtObject, null, undefined];

gtTestArr.indexOf("1");
// 0
gtTestArr.indexOf(1); // 1
gtTestArr.indexOf(true); // 2
gtTestArr.indexOf([66]); // -1
gtTestArr.indexOf(gtArray); // 4
gtTestArr.indexOf({ id: 1 }); //
-1
gtTestArr.indexOf(gtObject); // 6
gtTestArr.indexOf(null); // 7
gtTestArr.indexOf(undefined); //
8

从上述效果中看我们可以得出结论:indexOf 可以帮我们找到一个数组中某个元素(若该元素为数组或者对象,则为该引用的地址值)对应的索引值,在人脑“看”来相同的[66] 和 gtArray,实际上除了都用gtArray表示的部分是一样的,其他的 [66]之间以及gtArray都是不同的引用地址,自然也就找不到索引值啦 。

好了,回归正题,我们要进行数组去重,那么先想个大致的思路,比如:

1)新建一个空数组,老数组从第一个开始,看看新数组中有没有,如果没有就push进入新数组,如果存在就下一个。

2)在一个数组里面从第一个开始,将它后面的元素依次与当前这个比较,如果相等,就把后面的那个元素删掉,依次往复操作,直到最后一个。接着比较对象变成第二个,重复上述步骤,直到比较对象是最后一个。

3)and so on

当然每个思路有不同的算法,对于一种判断描述也可以有不同的实现方式(如下面的相等),比如用 map,用下标等。不同方式可能也会有不同的局限性或者前置条件。

好,现在我们界定一下什么是相等,简单的 1 与 1 肯定是相等的,而1 与 “1”是不等的,对于引用类型我们可以分为几种模式(级别):

1)仅引用地址一样才算相等。

2)引用地址可以不一样,但对应的数组(对象)所拥有的元素(键值对)一模一样就算相等。 即在我们看来,这两个数据写出来,看上去就是一样的。

3)对于是非数组的对象,针对几个key的值是一样的情况,我们将其认定是一样的。比如 { id: 1, name: ”张三” } 和 { id: 1, name: ”李四” } 在只考虑 id 字段时他们就是一样的。当然这种类型是我们人为赋予的模式。

好了,准备工作已做好,我们开始码代码吧。

按照思路1,相等的模型取第二种,直接上代码如下:

function gtUniqueArr(arr) {
var i,
newArr = [];

function isExist(_item, _arr) {
var k,
find = false;
if (typeof _item !== "object"
|| _item === null) {
return _arr.indexOf(_item) > -1;
}
for (k in _arr) {
if (_arr.hasOwnProperty(k)) {
find = isEqual(_item, _arr[k]);
if (find) {
break;
}
}
}
return find;
};
function isEqual(_a, _b) {
var k,
keysA,
keysB,
equal = true;
if (typeof _a !== "object" ||
_a === null ||
typeof _b !== "object" || _b === null) { // 有非引用类型(数组与对象)或者有NULL类型时直接判断
return _a === _b;
}
// _a _b 不同为数组或者对象时 直接认为不同,否则长得像数组的对象也会互判相等
if (_a instanceof Array !== _b
instanceof Array) {
return false;
}
// 同为对象或者数组
keysA = Object.keys(_a);
keysB = Object.keys(_b);
if (keysA.length !== keysB.length) { //
元素量不同肯定就不是一样了啊
return false;
}
// 其实也可以先判断下引用地址是否一样,一样肯定就相等啦
for (k in _a) {
if (_a.hasOwnProperty(k)) {
equal = isEqual(_a[k], _b[k]);
if (!equal) {
break;
}
}
}
return equal;
};

if (arr && arr.length) {
for (i = 0; i < arr.length; i++) {
if (!isExist(arr[i], newArr)) {
newArr.push(arr[i]);
}
}
}
return newArr;
}

我们可以把isExist,isEqual提取成公共函数,按照思路2,相等类型依然为第二种,上代码:

function gtUniqueArr(arr) {
var i, j;

if (arr && arr.length) {
for (i = 0; i < arr.length; i++) {
for (j = i + 1; j < arr.length;
j++) {
if (isEqual(arr[i], arr[j])) {
arr.splice(j, 1);
j--; // 复原因数组删除导致的遗漏了的元素指向
}
}
}
}
return arr;
}

当然,要采取不同的相等模式,只要改变 isEqual 函数即可,此处其他两种相等模式(或者你还有其他假设的相等模式)诉求相对较少,此处便不再展开叙述了(模式1,直接用===比较两者即可;模式3,用===检测要求的字段的值是否一样)。

当我们的环境是ES6时,一般的去重标准可以使用 set 来做:

var rs = new Set(arr);

但是当数组元素为引用类型时,引用地址不一样但在我们看来是完全一样的两个元素,这个方法是去不掉的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 浅谈移动端 View 的显示过程 顶

    随着科技的发展,各种移动端早已成为人们日常生活中不可或缺的部分,人们使用移动端产品工作、社交、娱乐……移动端界面的流畅性已经成为影响用户体验的重要因素之一。那么...

    个推君
  • 个推技术实现原理介绍

    概述 PUSH是互联网上内容提供者和内容定制方之间的一种通信机制,利用在服务器端的程序把数据源源不断地推向客户端,大大提高客户机和服务器之间的交互性能。 传统互...

    个推君
  • iOS13 即将到来,iOS 推送 DeviceToken 适配方案详解

    随着苹果iOS13系统即将发布,个推提前推出DeviceToken适配方案,以确保新版本的兼容与APP推送服务的正常使用。iOS13的一个重要变化是"[devi...

    个推君
  • 小兔JS教程(四)-- 彻底攻略JS数组

    剽悍一小兔
  • 数据结构与算法——稀疏数组

    当一个数组(包括多维数组)中的大部分元素为0或者为同一个数值的数组时,为了节约空间起到压缩的效果,将数据用另一种结构来表示,即稀疏数组。

    C you again 的博客
  • Python中的正则表达式(二)

    re.search():此方法返回None(如果模式不匹配),或者返回re.MatchObject,其中包含有关字符串的匹配部分的信息。此方法在第一个匹配项后停...

    PHP开发工程师
  • Python中的正则表达式(二)

    re.search():此方法返回None(如果模式不匹配),或者返回re.MatchObject,其中包含有关字符串的匹配部分的信息。此方法在第一个匹配项后...

    用户7466307
  • 【python正则】工作中常用的pyth

    # 4到16位(字母,数字,下划线,减号) if re.match(r'^[a-zA-Z0-9_-]{4,16}$', "abwc"):   print("匹...

    py3study
  • 实现类似“添加扩展程序…”的设计时支持

    Ajax Control Toolkit这个控件库内包含一些扩展控件,利用这些扩展控件,可以非常方便的为普通的控件添加Ajax效果,例如,利用AutoComp...

    明年我18
  • LeetCode 例题精讲 | 17 动态规划如何拆分子问题,简化思路

    在上一篇文章中,我们讲解了「子数组」类动态规划题目的常见技巧。这篇文章继续讲解动态规划问题中的小技巧。今天要讲的是「如何定义多个子问题」。

    五分钟学算法

扫码关注云+社区

领取腾讯云代金券