JavaScript学习笔记之数组去重,javascript学习笔记

推荐阅读:JavaScript学习笔记之数组的增、删、改、查

JavaScript学习笔记之数组去重,javascript学习笔记

推荐阅读:JavaScript学习笔记之数组的增、删、改、查

JavaScript学习笔记之数组求和方法

JavaScript学习笔记之数组随机排序

话说面试常会碰到面试官会问JavaScript实现数组去重的问题,最近刚好在学习有关于JavaScript数组相关的知识,趁此机会整理了一些有关于JavaScript数组去重的方法。

下面这些数组去重的方法是自己收集和整理的,如有不对希望指正文中不对之处。

双重循环去重

这个方法使用了两个for循环做遍历。整个思路是:

构建一个空数组用来存放去重后的数组

外面的for循环对原数组做遍历,每次从数组中取出一个元素与结果数组做对比
如果原数组取出的元素与结果数组元素相同,则跳出循环;反之则将其存放到结果数组中

代码如下:

Array.prototype.unique1 = function () {
// 构建一个新数组,存放结果
var newArray = [this[0]];
// for循环,每次从原数组中取出一个元素
// 用取出的元素循环与结果数组对比
for (var i = 1; i < this.length; i++) {
var repeat = false;
for (var j=0; j < newArray.length; j++) {
// 原数组取出的元素与结果数组元素相同
if(this[i] == newArray[j]) {
repeat = true;
break;
}
}
if(!repeat) {
// 如果结果数组中没有该元素,则存放到结果数组中
newArray.push(this[i]);
}
}
return newArray;
}

假设我们有一个这样的数组:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1',`2`];
arr.unique1(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5]

据说这种方法比较耗时,费性能。简单做个测试(测试方法写得比较拙逼):

function test () {
var arr = [];
for (var i = 0; i < 1000000; i++) {
arr.push(Math.round(Math.random(i) * 10000));
}
doTest(arr, 1);
}
function doTest(arr, n) {
var tStart = (new Date()).getTime();
var re = arr.unique1();
var tEnd = (new Date()).getTime();
console.log('双重循环去重方法使用时间是:' + (tEnd - tStart) + 'ms');
return re;
}
test();

在Chrome控制器运行上面的代码,测试双重循环去重所费时间:11031ms。

上面的方法可以使用forEach()方法和indexOf()方法模拟实现:

function unique1() {
var newArray = [];
this.forEach(function (index) {
if (newArray.indexOf(index) == -1) {
newArray.push(index);
}
});
return newArray;
}

通过unique1.apply(arr)或unique1.call(arr)调用。不过这种方法效率要快得多,同样的上面测试代码,所费时间5423ms,几乎快了一半。

排序遍历去重

先使用sort()方法对原数组做一个排序,排完序之后对数组做遍历,并且检查数组中的第i个元素与结果数组中最后一个元素是否相同。如果不同,则将元素放到结果数组中。

Array.prototype.unique2 = function () {
// 原数组先排序
this.sort();
// 构建一个新数组存放结果
var newArray = [];
for (var i = 1; i < this.length; i++) {
// 检查原数中的第i个元素与结果中的最后一个元素是否相同
// 因为排序了,所以重复元素会在相邻位置
if(this[i] !== newArray[newArray.length - 1]) {
// 如果不同,将元素放到结果数组中
newArray.push(this[i]);
}
}
return newArray;
}

例如:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique2(); // ["1", 1, 2, "2", 3, 32, 34, 4, 5, 56, "a", "b", "c"]

这种方法有两个特色:

去重后的数组会做排序,主要是因为原数在去重前做了排序

去重后的数组,与数字相同的数字字符无法区分,比如’1’和1

使用同样的方法,测试所费时间:1232ms。

对象键值对法

这种去重方法实现思路是:

创建一个JavaScript对象以及新数组

使用for循环遍历原数组,每次取出一个元素与JavaScript对象的键做对比

如果不包含,将存入对象的元素的值推入到结果数组中,并且将存入object对象中该属性名的值设置为1

代码如下:

Array.prototype.unique3 = function () {
// 构建一个新数组存放结果
var newArray = [];
// 创建一个空对象
var object = {};
// for循环时,每次取出一个元素与对象进行对比
// 如果这个元素不重复,则将它存放到结果数中
// 同时把这个元素的内容作为对象的一个属性,并赋值为1,
// 存入到第2步建立的对象中
for (var i = 0; i < this.length; i++){
// 检测在object对象中是否包含遍历到的元素的值
if(!object[typeof(this[i]) + this[i]]) {
// 如果不包含,将存入对象的元素的值推入到结果数组中
newArray.push(this[i]);
// 如果不包含,存入object对象中该属性名的值设置为1
object[typeof(this[i]) + this[i]] = 1;
}
}
return newArray;
}

运行前面的示例:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique3(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]

同样的,不同的键可能会被误认为一样;例如: a[1]、a[“1”]
。这种方法所费时间:621ms。
这种方法所费时间是最短,但就是占用内存大一些。

除了上面几种方法,还有其他几种方法如下:

// 方法四
Array.prototype.unique4 = function () {
// 构建一个新数组存放结果
var newArray = [];
// 遍历整个数组
for (var i = 0; i < this.length; i++) {
// 遍历是否有重复的值
for (j = i + 1; j < this.length; j++) {
// 如果有相同元素,自增i变量,跳出i的循环
if(this[i] === this[j]) {
j = ++i;
}
}
// 如果没有相同元素,将元素推入到结果数组中
newArray.push(this[i]);
}
return newArray;
}

Chrome测试结果

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique4(); // ["a", 1, 3, 4, 56, 32, 34, 2, "b", "c", 5, "1", "2"]

同样的,1和’1’无法区分。

// 方法五
Array.prototype.unique5 = function () {
// 构建一个新数组存放结果
var newArray = [];
// 遍历整个数组
for (var i = 0; i < this.length; i++) {
// 如果当前数组的第i值保存到临时数组,那么跳过
var index = this[i];
// 如果数组项不在结果数组中,将这个值推入结果数组中
if (newArray.indexOf(index) === -1) {
newArray.push(index);
}
}
return newArray;
}

Chrome测试结果:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique6(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]

同样的,类似于1和’1’无法区分。所费时间:14361ms。

// 方法六
Array.prototype.unique6 = function () {
return this.reduce(function (newArray, index) {
if(newArray.indexOf(index) < 0) {
newArray.push(index);
}
return newArray;
},[]);
}

测试结果如下:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique6(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]

所费时间:16490ms。

// 方法七
Array.prototype.unique7 = function(){
var newArray;
newArray = this.filter(function (ele,i,arr) {
return arr.indexOf(ele) === i;
});
return newArray;
}

测试结果:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique6(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]

所费时间:13201ms。

方法虽然很多种,但相比下来,下面这种方法是较为优秀的方案:

Array.prototype.unique3 = function () {
// 构建一个新数组存放结果
var newArray = [];
// 创建一个空对象
var object = {};
// for循环时,每次取出一个元素与对象进行对比
// 如果这个元素不重复,则将它存放到结果数中
// 同时把这个元素的内容作为对象的一个属性,并赋值为1,
// 存入到第2步建立的对象中
for (var i = 0; i < this.length; i++){
// 检测在object对象中是否包含遍历到的元素的值
if(!object[typeof(this[i]) + this[i]]) {
// 如果不包含,将存入对象的元素的值推入到结果数组中
newArray.push(this[i]);
// 如果不包含,存入object对象中该属性名的值设置为1
object[typeof(this[i]) + this[i]] = 1;
}
}
return newArray;
}

但在ES6去重还有更简单,更优化的方案,比如:

// ES6
function unique (arr) {
const seen = new Map()
return arr.filter((a) => !seen.has(a) && seen.set(a, 1))
}
// or
function unique (arr) {
return Array.from(new Set(arr))
}

以上所述是小编给大家介绍的JavaScript学习笔记之数组去重,希望对大家有所帮助!

方法一:双重遍历

JavaScript学习笔记之数组求和方法

您可能感兴趣的文章:

  • javascript数字数组去重复项的实现代码
  • 两种常用的javascript数组去重方法思路及代码
  • javascript数组去重3种方法的性能测试与比较
  • js取两个数组的交集|差集|并集|补集|去重示例代码
  • js算法中的排序、数组去重详细概述
  • js实现数组去重、判断数组以及对象中的内容是否相同
  • 两个数组去重的JS代码
  • js数组去重的三种常用方法总结
  • 关于js数组去重的问题小结

推荐阅读: JavaScript学习笔记之数组的增、删、改、查
JavaScript学习笔记之数组求和方法 J…

双重遍历是最容易想到的去重方案:

JavaScript学习笔记之数组随机排序

  1. 构建一个新的数组存放结果
  2. for循环中每次从原数组取出一个元素,用这个元素循环与结果数组对比
  3. 若结果数组中没有该元素,则存到结果数组中

    Array.prototype.unique=function(){

    // 构建一个新数组,存放结果 
    var newArray = [this[0]];
    for (var i = 0; i<this.length; i++){
        var repeat = false;
        for(var j=0;j<newArray.length;j++){
            if(this[i]===newArray[j]){
                repeat=true;
                break;
            }
        }
        if(!repeat){
            newArray.push(this[i]);
        }
    }
    return newArray;
    

    }

话说面试常会碰到面试官会问JavaScript实现数组去重的问题,最近刚好在学习有关于JavaScript数组相关的知识,趁此机会整理了一些有关于JavaScript数组去重的方法。

  • 优点:思路简单、容易实现,用于去重的比较部分是自己编写实现(this[i]==newArray[j])。可以针对具体情况加以特殊处理。
  • 缺点:时间复杂度高,性能差。

下面这些数组去重的方法是自己收集和整理的,如有不对希望指正文中不对之处。

以下面这个测试案例进行比较:

双重循环去重

function test () { 
    var arr = []; 
    for (var i = 0; i < 1000000; i++) { 
        arr.push(Math.round(Math.random(i) * 10000)); 
    } 
    doTest(arr, 1); 
} 
function doTest(arr, n) { 
    var tStart = (new Date()).getTime(); 
    var re = arr.unique(); 
    var tEnd = (new Date()).getTime(); 
    console.log('双重循环去重方法使用时间是:' + (tEnd - tStart) + 'ms'); 
    return re; 
} 
test();

这个方法使用了两个for循环做遍历。整个思路是:

在Chrome控制台中测试方法一,花费时间为:4006ms

构建一个空数组用来存放去重后的数组

方法二:排序遍历去重

先使用sort()方法对原数组做一个排序,排完序之后对数组做遍历,并且检查数组中的第i个元素与结果数组中最后一个元素是否相同。如果不同,则将元素放到结果数组中。

Array.prototype.unique = function () { 
    // 原数组先排序 
    this.sort(); 
    // 构建一个新数组存放结果 
    var newArray = []; 
    for (var i = 1; i < this.length; i++) { 
    // 检查原数组中的第i个元素与结果中的最后一个元素是否相同 
    // 因为排序了,所以重复元素会在相邻位置 
        if(this[i] !== newArray[newArray.length - 1]) { 
        // 如果不同,将元素放到结果数组中 
            newArray.push(this[i]); 
        } 
    } 
    return newArray; 
}
  • 优点:速度快,只需要700ms
  • 缺点:去重后的数组会做排序、去重后的数组,与数字相同的数字字符无法区分,比如'12'12

外面的for循环对原数组做遍历,每次从数组中取出一个元素与结果数组做对比
如果原数组取出的元素与结果数组元素相同,则跳出循环;反之则将其存放到结果数组中

方法三:对象键值对法

这种方法是利用了对象的key不可以重复的特性来进行去重。

  1. 创建一个JavaScript对象及新数组
  2. 使用for循环遍历原数组,每次取出一个元素与JavaScript对象的键做对比
  3. 如果不包含,将存入对象的元素值推入到结果数组中,并且将存入对象的该key的value设为1

    Array.prototype.unique=function() {

    var ret = [];
    var len = this.length;
    var tmp = {};
    for(var i=0; i<len; i++){
        if(!tmp[this[i]]){
            tmp[this[i]] = 1;
            ret.push(this[i]);
        }
    }
    return ret;
    

    }

  • 优点:速度快,只需要10ms
  • 缺点:去重后的数组,与数字相同的数字字符无法区分,比如'12'12,因为对象key只能为字符串;无法处理复杂数据类型,比如对象(因为对象作为key会变成[object
    Object]);特殊数据,比如’proto‘会挂掉,因为tmp对象的’proto‘属性无法被重写

基于上面提到的缺点,有人提出了以下的改进措施:

Array.prototype.unique=function() {
    var ret = [];
    var len = this.length;
    var tmp = {};
    var tmpKey;
    for(var i=0; i<len; i++){
        tmpKey = typeof this[i] + JSON.stringify(this[i]);
        if(!tmp[tmpKey]){
            tmp[tmpKey] = 1;
            ret.push(this[i]);
        }
    }
    return ret;
}

这个改进方法可以弥补上述提到的缺点,但是性能有所降低,去重速度达到了500ms左右,且内存占用较高,但依然是各个方案中最快的。

代码如下:

方法四:Map Key

ES2015中添加了Map这种新的数据类型,可以把它想象成key类型没有限制的对象,它的存取使用单独的get()、set()接口。与传统的对象相比,Map的key在使用中没有限制。

Array.prototype.unique=function() {
    var ret = [];
    var len = this.length;
    var tmp = new Map();
    for(var i=0; i<len; i++){
        if(!tmp.get(this[i])){
            tmp.set(this[i], 1);
            ret.push(this[i]);
        }
    }
    return ret;
}
  • 优点:执行速度快,43ms
  • 缺点:兼容性不高。
Array.prototype.unique1 = function () {
// 构建一个新数组,存放结果
var newArray = [this[0]];
// for循环,每次从原数组中取出一个元素
// 用取出的元素循环与结果数组对比
for (var i = 1; i < this.length; i++) {
var repeat = false;
for (var j=0; j < newArray.length; j++) {
// 原数组取出的元素与结果数组元素相同
if(this[i] == newArray[j]) {
repeat = true;
break;
}
}
if(!repeat) {
// 如果结果数组中没有该元素,则存放到结果数组中
newArray.push(this[i]);
}
}
return newArray;
}

方法五:Set

除了Map以外,ES2015还引入了一种叫作Set的数据类型。它不允许重复元素出现。

Array.prototype.unique=function(){
    var set = new Set(this);
    return Array.from(set);
}
  • 优点:代码简单,执行速度较快,600ms左右。
  • 缺点:兼容性不高。

假设我们有一个这样的数组:

总结

去重的方法没有最正确的,也没有最优,应该具体问题具体分析,根据实际场景进行选择正确的方法。

请使用手机”扫一扫”x

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1',`2`];
arr.unique1(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5]

据说这种方法比较耗时,费性能。简单做个测试(测试方法写得比较拙逼):

function test () {
var arr = [];
for (var i = 0; i < 1000000; i++) {
arr.push(Math.round(Math.random(i) * 10000));
}
doTest(arr, 1);
}
function doTest(arr, n) {
var tStart = (new Date()).getTime();
var re = arr.unique1();
var tEnd = (new Date()).getTime();
console.log('双重循环去重方法使用时间是:' + (tEnd - tStart) + 'ms');
return re;
}
test();

在Chrome控制器运行上面的代码,测试双重循环去重所费时间:11031ms。

上面的方法可以使用forEach()方法和indexOf()方法模拟实现:

function unique1() {
var newArray = [];
this.forEach(function (index) {
if (newArray.indexOf(index) == -1) {
newArray.push(index);
}
});
return newArray;
}

通过unique1.apply(arr)或unique1.call(arr)调用。不过这种方法效率要快得多,同样的上面测试代码,所费时间5423ms,几乎快了一半。

排序遍历去重

先使用sort()方法对原数组做一个排序,排完序之后对数组做遍历,并且检查数组中的第i个元素与结果数组中最后一个元素是否相同。如果不同,则将元素放到结果数组中。

Array.prototype.unique2 = function () {
// 原数组先排序
this.sort();
// 构建一个新数组存放结果
var newArray = [];
for (var i = 1; i < this.length; i++) {
// 检查原数中的第i个元素与结果中的最后一个元素是否相同
// 因为排序了,所以重复元素会在相邻位置
if(this[i] !== newArray[newArray.length - 1]) {
// 如果不同,将元素放到结果数组中
newArray.push(this[i]);
}
}
return newArray;
}

例如:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique2(); // ["1", 1, 2, "2", 3, 32, 34, 4, 5, 56, "a", "b", "c"]

这种方法有两个特色:

去重后的数组会做排序,主要是因为原数在去重前做了排序

去重后的数组,与数字相同的数字字符无法区分,比如’1’和1

使用同样的方法,测试所费时间:1232ms。

对象键值对法

这种去重方法实现思路是:

创建一个JavaScript对象以及新数组

使用for循环遍历原数组,每次取出一个元素与JavaScript对象的键做对比

如果不包含,将存入对象的元素的值推入到结果数组中,并且将存入object对象中该属性名的值设置为1

代码如下:

Array.prototype.unique3 = function () {
// 构建一个新数组存放结果
var newArray = [];
// 创建一个空对象
var object = {};
// for循环时,每次取出一个元素与对象进行对比
// 如果这个元素不重复,则将它存放到结果数中
// 同时把这个元素的内容作为对象的一个属性,并赋值为1,
// 存入到第2步建立的对象中
for (var i = 0; i < this.length; i++){
// 检测在object对象中是否包含遍历到的元素的值
if(!object[typeof(this[i]) + this[i]]) {
// 如果不包含,将存入对象的元素的值推入到结果数组中
newArray.push(this[i]);
// 如果不包含,存入object对象中该属性名的值设置为1
object[typeof(this[i]) + this[i]] = 1;
}
}
return newArray;
}

运行前面的示例:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique3(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]

同样的,不同的键可能会被误认为一样;例如: a[1]、a[“1”]
。这种方法所费时间:621ms。
这种方法所费时间是最短,但就是占用内存大一些。

除了上面几种方法,还有其他几种方法如下:

// 方法四
Array.prototype.unique4 = function () {
// 构建一个新数组存放结果
var newArray = [];
// 遍历整个数组
for (var i = 0; i < this.length; i++) {
// 遍历是否有重复的值
for (j = i + 1; j < this.length; j++) {
// 如果有相同元素,自增i变量,跳出i的循环
if(this[i] === this[j]) {
j = ++i;
}
}
// 如果没有相同元素,将元素推入到结果数组中
newArray.push(this[i]);
}
return newArray;
}

Chrome测试结果

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique4(); // ["a", 1, 3, 4, 56, 32, 34, 2, "b", "c", 5, "1", "2"]

同样的,1和’1’无法区分。

// 方法五
Array.prototype.unique5 = function () {
// 构建一个新数组存放结果
var newArray = [];
// 遍历整个数组
for (var i = 0; i < this.length; i++) {
// 如果当前数组的第i值保存到临时数组,那么跳过
var index = this[i];
// 如果数组项不在结果数组中,将这个值推入结果数组中
if (newArray.indexOf(index) === -1) {
newArray.push(index);
}
}
return newArray;
}

Chrome测试结果:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique6(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]

同样的,类似于1和’1’无法区分。所费时间:14361ms。

// 方法六
Array.prototype.unique6 = function () {
return this.reduce(function (newArray, index) {
if(newArray.indexOf(index) < 0) {
newArray.push(index);
}
return newArray;
},[]);
}

测试结果如下:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique6(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]

所费时间:16490ms。

// 方法七
Array.prototype.unique7 = function(){
var newArray;
newArray = this.filter(function (ele,i,arr) {
return arr.indexOf(ele) === i;
});
return newArray;
}

测试结果:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique6(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]

所费时间:13201ms。

方法虽然很多种,但相比下来,下面这种方法是较为优秀的方案:

Array.prototype.unique3 = function () {
// 构建一个新数组存放结果
var newArray = [];
// 创建一个空对象
var object = {};
// for循环时,每次取出一个元素与对象进行对比
// 如果这个元素不重复,则将它存放到结果数中
// 同时把这个元素的内容作为对象的一个属性,并赋值为1,
// 存入到第2步建立的对象中
for (var i = 0; i < this.length; i++){
// 检测在object对象中是否包含遍历到的元素的值
if(!object[typeof(this[i]) + this[i]]) {
// 如果不包含,将存入对象的元素的值推入到结果数组中
newArray.push(this[i]);
// 如果不包含,存入object对象中该属性名的值设置为1
object[typeof(this[i]) + this[i]] = 1;
}
}
return newArray;
}

但在ES6去重还有更简单,更优化的方案,比如:

// ES6
function unique (arr) {
const seen = new Map()
return arr.filter((a) => !seen.has(a) && seen.set(a, 1))
}
// or
function unique (arr) {
return Array.from(new Set(arr))
}

以上所述是小编给大家介绍的JavaScript学习笔记之数组去重,希望对大家有所帮助!

您可能感兴趣的文章:

  • JavaScript中的Number数字类型学习笔记
  • JavaScript继承学习笔记【新手必看】
  • JavaScript自学笔记(必看篇)
  • Javascript基础学习笔记(菜鸟必看篇)

Post Author: admin

发表评论

电子邮件地址不会被公开。 必填项已用*标注