'javascript-数组去重'

2018-01-10

Javascipt数组去重

方法一: 双循环（时间复杂度比较高, 性能一般。）

测试用例一

var arr = [1, 2, 3, 1];
function unique (arr) {
  var newArr = [];
  var len = arr.length;
  var isRepeat;
  for (var i = 0; i < len; i++) {
    isPepeat = false;
    // console.log(arr[i], 'arr[i]');
    for (var j = i + 1; j < len; j++) {
      // console.log(arr[j], '111');
      console.log(arr[i], 'arr[i]');
      console.log(arr[j], 'arr[j]');         
      if (arr[i] === arr[j]) {
        isPepeat = true;
        break;
      }
    }
    if (!isPepeat) {
      newArr.push(arr[i]);
    }
  }
  return newArr;
}
console.log(unique(arr)); //  [2, 3, 1]

测试用例二

function unique(arr) {
  var newArr = [];
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    for (var j = i + 1; j < len; j++) {
      // console.log(j);
      if (arr[i] === arr[j]) {   
        j = ++i;  //  不理解这里的意思,恕我愚钝
      }
    }
    // console.log(arr[i]);
    newArr.push(arr[i]);
  }
  return newArr;
}
console.log(unique(arr)); //  [2, 3, 1]

tip: j = ++i;等价于 j = j + 1; i = i + 1；
整体思路就是如果是重复元素,则跳过重复元素,不对其进行push操作。

方法二: Array.prototype.indexOf()

测试用例三

function unique(arr) {
  return arr.filter(function(item, index) {
    // console.log(item);
    console.log(index);
    console.log(arr.indexOf(item));
    //  其中indexOf代表着item里面第一次出现的位置,
    //  这样的话返回的也是所有第一次出现的元素。恩,对,没错。
    return arr.indexOf(item) === index;
  });
}
console.log(unique(arr)); //  [1, 2, 3]

tip: var new_array = arr.filter(callback, [thisArg])
callback: 用来测试数组的每个元素的函数,调用时使用参数(element,index, array)。
返回true表示保留该元素(通过测试),false则不保留。
thiArg: 可选。执行callback时的用于this的值。
整体思路就是索引不是第一个索引,说明是重复值。

详情见:
MDN-filter

测试用例四

function unique(arr) {
  var newArr = [];
  arr.forEach((element) => {
    console.log(newArr);
    console.log(newArr.indexOf(element));
    if (newArr.indexOf(element) === -1) {
      newArr.push(element);
    }
  });
  return newArr;
}
console.log(unique(arr)); //  [1, 2, 3]

tip: indexOf在这里代表着,当newArr里没有这个元素所以返回了-1,
而当newArr没有重复元素时,indexOf返回的都是-1。
整体思路为当没有没有重复元素返回-1,满足条件成立返回出去

详情见:
MDN-indexOf

方法三: Array.prototype.sort()

测试用例五

function unique(arr) {
  var newArr = [];
  arr.sort();
  console.log(arr);
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] !== arr[i + 1]) {
      newArr.push(arr[i]);
    }
  }
  return newArr;
}
unique(arr); // [1, 2, 3]

tip: 原理就是按照排序的方式进行排序如[1, 2, 3, 1, 3]排序过后
就会形成[1, 1, 2, 3, 3]。当然这里有一个问题是sort对于其他
比如说[1, 11, 22, 18]就不会按照你设想的去排序,它会排序为
[1, 11, 18, 22]。然后就是进行判断相邻的(相邻的比如1, 1)
如果不相等就push然后返回。恩完美。

详情见:
MDN-sort

测试用例六

function unique(arr) {
  var newArr = [];
  arr.sort();
  for (var i = 0; i < arr.length; i++) {
    // console.log(arr[i]);
    console.log(arr[i], newArr[newArr.length - 1]);
    // console.log(arr[i]);              
    if (arr[i] !== newArr[newArr.length - 1]) {
      // console.log(arr[i]);                    
      newArr.push(arr[i]);
    }
  }
  return newArr;
}
unique(arr);  //  [1, 2, 3]

tip: 这里利用到的是与数组的进行比对,如果匹配不成功则push。
这里的点是进行第一次比对时因为数组为空那么它的长度-1就是undefined，
然后push了1进入。第二次比对发现长度-1与arr[i]匹配成功,条件不满足。
进行第三次匹配,以此类推。

方法四: 使用对象key来去重

测试用例7

function unique(arr) {
  var newArr = [];
  var len = arr.length;
  var tmp = {};
  for (var i = 0; i < len; i++) {
    console.log(tmp);
    if (!tmp[arr[i]]) {     
      // console.log(tmp[arr[i]]);
      tmp[arr[i]] = 1;
      // console.log(tmp);
      newArr.push(arr[i]);
    }
  } 
  return newArr;
}
unique(arr);

tip: 这里利用了对象(tmp)的key不可以重复的特性进行去重。
当进行匹配的时候默认情况下,是不存在tmp[arr[i]]的,
符合条件进行复制与push。循环往复。当有重复的元素时,
条件不满足。结束。

注意问题: // 更新一下问题明白了。
// 这里我不太理解,希望有明白的能给解释下。

- 无法区分隐式类型转换成字符后一样的值, 比如1和'1'。
- 无法处理复杂数据类型, 比如对象(因为对象作为key会变成[object Object])。
- 特殊数据, 比如'_proto_'会挂掉,因为tmp对象的_proto_属性无法被重写。

解决1, 3: 可以为对象的key增加一个类型,或者将类型放到对象的value中来解决:

测试用例8

function unique(arr) {
  var newArr = [];
  var len = arr.length;
  var tmp = {};
  var tmpKey;
  for(var i=0; i < len; i++){
      tmpKey = typeof arr[i] + arr[i];

      console.log(tmpKey); 

      if(!tmp[tmpKey]){
          tmp[tmpKey] = 1;
          newArr.push(arr[i]);
      }
  }
  return newArr;
}
console.log(unique(arr)); //  [1,2,3]

text
这里换成了 var arr = [{xiaoming:23,xiaoqing:45},{xiaoming:24,xiaoqing:45}];
text

解决问题二: 可以把对象序列化之后作为key来使用。这里使用了JSON.stringify()进行序列化。

测试用例9

function unique(arr) {
  var newArr = [];
  var len = arr.length;
  var tmp = {};
  var tmpKey;
  for(var i=0; i < len; i++){
      tmpKey = typeof arr[i] + JSON.stringify(arr[i]);
      // console.log(tmpKey); 
      if(!tmp[tmpKey]){
          tmp[tmpKey] = 1;
          newArr.push(arr[i]);
      }
  }
  return newArr;
}
console.log(unique(arr));

text

ES6

方法一: Map

function unique(arr) {
  var newArr = [];
  var len = arr.length;
  var tmp = new Map();
  for (var i = 0; i < len; i++) {
    if (!tmp.get(arr[i])) {
      tmp.set(arr[i], 1);
      newArr.push(arr[i]);
    }
  }
  return newArr;
}
unique(arr);  //  [1, 2, 3]

tip: 这里用的是ES6-Map,是一种新的数据类型,类似于对象, 也是键值对的集合, 但是”键”的范围不限于字符串,
各种类型的值(包括对象)都可以当做键。可以把它想象成key类型没有限制的对象。它的存取使用单独的get()
set()接口。
这里的方法也是进行判断tmp数组get有没有key与value如果没有就push,如果有判断条件不成立。

方法二: Set

function unique(arr) {
  var set = new Set(arr);
  return Array.from(set);
}
console.log(unique(arr)); //  [1, 2, 3]

tip: Set是一种新的数据结构。它类似与数组,但是成员的值都是唯一的,没有重复的值。
Array.from方法从类似数组或可迭代对象创建一个新的数组实例。
也可以使用扩展运算符 return […set]与Array.from同理。

方法三: Array.prototype.includes

function unique(arr) {
  var newArr = [];
  arr.forEach((element) => {
    console.log(newArr.includes(element));
    if (!newArr.includes(element)) {
      newArr.push(element);
    }
  });
  return newArr;
}
console.log(unique(arr)); //  [1, 2, 3]

tip: includes方法用来判断一个数组是否包含一个指定的值,如果包含则返回true,
否则返回false。恩,就是这样。

纯手打。

加了一些自己的理解。后续还会加入更多关于数组去重的方法。就这样,溜了。。。

o.o