去重

2018-03-18

剑指offer与一些经典数据结构算法。(js写）

数组去重

1、最基本的，双层嵌套循环（里面可以用splice删去重复元素或新建一个数组把不重复的值push进去）。（太简单就不写了）

2、ES6的set数据结构

function unique (arr) {
  return Array.from(new Set(arr))
}

3、先排序，然后将每一项和前一项比较，如果不同，push进新数组。

4、使用对象的属性不可相同的特点，定义一个对象，将数组的值附到对象的值上。

思路：每次取出原数组的元素，然后再对象中访问这个属性，如果存在就说明重复

function unique(arr){

  var res =[];

  var json = {};

  for(var i=0;i<arr.length;i++){

    if(!json[arr[i]]){

      res.push(arr[i]);

      json[arr[i]] = 1;

    }

  }
  return res;
}

5、每个数组下标对应相同的数字，这个思路来解。将原数组的每一项赋值给另一个数组的对应下标，比如a[0]=1，则把b[1]=a[0]=1,a[1]=5,b[5]=a[1]=5，也就是辅助数组b的每一项下标都跟数据相等，这样就很容易判别给定a数组中的重复数字了（因为每一项在b数组中只有唯一1个下标对应）。

function duplicate(a)
{
    var b=[];
    for(var i=0;i<a.length;i++){
        if(!b[a[i]]){
            b[a[i]]=a[i];
        }
    }
    for(var i=0;i<b.length;i++){
        if(!b[i]){
        b.splice(i,1);
        }
    }
    return b;
}