数组去重

2017-12-17

摘要：JavaScript面试题数组去重，参考冴羽的博客再次修改

方法一

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

Array.prototype.unique1_1 = function () {
  var res = [];
  for (var i = 0, len = this.length; i < len; i++) {
    for (var j = 0, reslen = res.length; j < reslen; j++) { // 依次与结果数组的值比较
      if (this[i] === res[j]) { // 值相同跳出
        break;
      }
    }
    // 当j与reslen相等时，说明上面的循环全部执行，并没有匹配到相同的值
    if (j === reslen) {
      res.push(this[i]);
    }
  }
  return res;
}

使用indexOf简化内层的循环：

Array.prototype.unique1_2 = function () {
  var res = [];
  for (var i = 0, len = this.length; i < len; i++) { // 从第二个开始一次获取目标数组的值
    if (res.indexOf(this[i]) === -1) {
      res.push(this[i])
    }
  }
  return res;
}

使用filter简化外层循环：

Array.prototype.unique1_3 = function () {
  var res = this.filter(function (item, index) {
    return this.indexOf(item) === index;
  }, this)
  return res;
}

方法二

思路：
1.将目标组进行排序后存储到一个新数组中
2.检查排序后新数组中的第i个元素与结果数组中的最后一个元素是否相同，因为已经排序，所以重复元素会在相邻位置
3.如果不相同，则将该元素存入结果数组中

Array.prototype.unique2_1 = function () {
  var array = this.concat().sort(); // concat方法返回一个数组副本后再进行排序，避免改变原数组
  var res = [];
  for (var i = 0, len = array.length; i < len; i++) {
    if (array[i] !== res[res.length - 1]) {
      res.push(array[i]);
    }
  }
  return res;
}

使用filter简化：

Array.prototype.unique2_2 = function () {
  var array = this.concat().sort();
  return res = array.filter(function (item, index, array) {
    return !index || item !== array[index - 1]
  })
}

现在数组有两种情况：有序和无序。结合前两种方法，为了提高去重效率可以这样写：

Array.prototype.unique2_3 = function (isSorted) { // 有序数组为true，无序为false
  var res = [];
  var last = [];
  for (var i = 0, len = this.length; i < len; i++) {
    var value = this[i];
    // 如果是排序后的数组，直接比较相邻的两个值
    // 如果是无序的数组，使用indexOf匹配
    if (isSorted) {
      if (!i || last !== value) {
        res.push(value);
      }
      last = value;
    } else if (res.indexOf(value) === -1) {
      res.push(value);
    }
  }
  return res;
}

如果还有不区分字母大小写等需求，可以先将所有字符转小写再按照前面的方法处理，但这样先遍历一次数组的效率并不高。想要在去重比较的同时进行处理：

Array.prototype.unique12_4 = function (isSorted, callback) {
  var res = []; // 存储没处理过的元素，大小写都可能有
  var last = []; // 存储处理过的元素，只会是小写
  for (var i = 0, len = this.length; i < len; i++) {
    var value = this[i];
    var computed = callback ? callback(value, i, this) : value; // 获得处理后的元素
    if (isSorted) { // 有序，当字母大小写紧挨着（AaBb）时是区分大小写的，当不挨着（ABab）时是不区分的，主要看自己规定的什么顺序是“有序”，可以只保留下面两个判断
      if (!i || last !== computed) {
        res.push(value)
      }
      last = computed;
    } else if (callback) { // 无序不区分大小写
      if (last.indexOf(computed) === -1) {
        last.push(computed);
        res.push(value);
      }
    } else if (res.indexOf(value) === -1) { // 无序区分大小写
      res.push(value);
    }
  }
  return res;
}
// 调用
array.unique(false, function (item) {
  return typeof item == "string" ? item.toLowerCase() : item
})

方法三

思路：
1.创建一个新的数组存放结果
2.创建一个空对象
3.for循环时，每次取出一个元素与对象进行对比，如果这个元素不重复（对象没有这个属性），则把它存放到结果数组中，同时把这个元素的内容作为对象的一个属性，并赋值为true，存入到第2步创建的对象中。

Array.prototype.unique3_1 = function () {
  var res = [];
  var obj = {};
  for (var i = 0, len = this.length; i < len; i++) {
    if (!obj.hasOwnProperty(this[i])) {
      res.push(this[i]);
      obj[this[i]] = true;
    }
  }
  return res;
}

使用filter简化：

Array.prototype.unique3_2 = function () {
  var obj = {};
  return this.filter(function (item, index) {
    return obj.hasOwnProperty(item) ? false : (obj[item] = true);
  })
}

数组值的类型不都一样的话会程序有一点问题：数字 1 和字符串”1”会认为是一个属性，因为对象的键都是字符串。这时就需要区分两者，可以添加特定的字符串加以区别。比如添加上各自的类型：

Array.prototype.unique3_3 = function () {
  var obj = {};
  return this.filter(function (item, index) {
    return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true);
  })
}
// obj = {
//   number1: true,
//   string1: true
// }

但是，依然无法正确区分出两个对象，因为 typeof item +item 的结果都是object[object Object]，可以使用JSON.stringify将对象序列化加以区别：

Array.prototype.unique3_4 = function () {
  var obj = {};
  return this.filter(function (item) {
    return obj.hasOwnProperty(typeof item + JSON.stringify(item)) ? false : (obj[typeof item + JSON.stringify(item)] = true)
  })
}

如果要统计每个值重复的次数，需要进行修改，用参数count来判断返回什么值

Array.prototype.unique3_5 = function (count) {
  var obj = {};
  var res = this.filter(function (item) {
    if (obj.hasOwnProperty(typeof item + JSON.stringify(item))) {
      obj[typeof item + JSON.stringify(item)]++
      return false;
    } else {
      obj[typeof item + JSON.stringify(item)] = 1;
      return true;
    }
  })
  return count ? obj : res;
}

方法四

利用 Set 结构的成员值不能重复的特点来实现数组去重的效果

Array.prototype.unique4_1 = function(){
  // return this.from(new Set(this));
  return [...new Set(this)];
}

还可以利用Map的键名可以是各种类型的特点来实现

Array.prototype.unique4_2 = function() {
  const map = new Map()
  return this.filter((a) => !map.has(a) && map.set(a, 1))
}

总结

使用这样一个数组 array 进行验证：

1	var array = [1, 1, "1", "1", null, null, undefined, undefined, new String("1"), new String("1"), /a/, /a/, NaN, NaN];

方法	结果	结论
1_1：for循环	[1, “1”, null, undefined, String, String, /a/, /a/, NaN, NaN]	对象和NaN不去重
1_2：indexOf	[1, “1”, null, undefined, String, String, /a/, /a/, NaN, NaN]	对象和 NaN 不去重
1_3：filter + indexOf	[1, “1”, null, undefined, String, String, /a/, /a/]	对象不去重 NaN 被忽略
2_1：sort	[/a/, /a/, “1”, 1, String, 1, String, NaN, NaN, null, undefined]	对象、NaN、数字1不去重
2_2：sort + filter	[/a/, /a/, “1”, 1, String, 1, String, NaN, NaN, null, undefined]	对象、NaN、数字1不去重
3_4：优化后的键值对	[1, “1”, null, undefined, String, /a/, NaN]	全部去重
4_1：Set（node）	[1, “1”, null, undefined, [String: “1”], [String: “1”], /a/, /a/, NaN]	对象不去重

注意：
1.indexOf使用strict equality(无论是===，还是triple-equals操作符都基于同样的方法)进行判断 searchElement与数组中包含的元素之间的关系
2.NaN和undefined都可以被存储在Set中，尽管NaN !== NaN，但NaN之间仍被视为相同的值
3.优化后的计数：

console.log(array.unique3_5(true));
// {
//   number1:2,
//   numbernull:2,
//   object"1":2,
//   objectnull:2,
//   object{}:2,
//   string"1":2,
//   undefinedundefined:2,
// }