微信号:FrontDev

介绍:分享 Web 前端相关的技术文章、工具资源、精选课程、热点资讯

也谈面试必备问题之 JavaScript 数组去重

2016-06-10 19:49 前端大全

(点击上方公众号,可快速关注)

作者:伯乐在线专栏作者 - 韩子迟

链接:http://web.jobbole.com/86360/

点击 → 了解如何加入专栏作者


数组去重


今天要聊的,也是我以前笔试时碰到过的一个问题,数组去重,不知道现在的笔试题还考不考这个?


数组去重,一般需求是给你一个数组,调用去重方法,返回数值副本,副本中没有重复元素。一般来说,两个元素通过 === 比较返回 true 的视为相同元素,需要去重,所以,1 和 "1" 是不同的元素,1 和 new Number(1) 是不同的元素,{} 和 {} 是不同的元素(引用不同)。(当然如果需求认为 {} 和 {} 算作相同的元素,那么解法就不一样了)


方法一


无需思考,我们可以得到 O(n^2) 复杂度的解法。定义一个变量数组 res 保存结果,遍历需要去重的数组,如果该元素已经存在在 res 中了,则说明是重复的元素,如果没有,则放入 res 中。


function unique(a) {

  var res = [];

 

  for (var i = 0, len = a.length; i < len; i++) {

    var item = a[i];

 

    for (var j = 0, jLen = res.length; j < jLen; j++) {

      if (res[j] === item)

        break;

    }

 

    if (j === jLen)

      res.push(item);

  }

 

  return res;

}

 

var a = [1, 1, '1', '2', 1];

var ans = unique(a);

console.log(ans); // => [1, "1", "2"]


代码非常简单,那么是否能更简洁些?如果不考虑浏览器兼容,我们可以用 ES5 提供的 Array.prototype.indexOf 方法来简化代码。


function unique(a) {

  var res = [];

 

  for (var i = 0, len = a.length; i < len; i++) {

    var item = a[i];

 

    (res.indexOf(item) === -1) && res.push(item);

  }

 

  return res;

}

 

var a = [1, 1, '1', '2', 1];

var ans = unique(a);

console.log(ans); // => [1, "1", "2"]


既然用了 indexOf,那么不妨再加上 filter。


function unique(a) {

 

  var res = a.filter(function(item, index, array) {

    return array.indexOf(item) === index;

  });

  

  return res;

}

 

 

var a = [1, 1, '1', '2', 1];

var ans = unique(a);

console.log(ans); // => [1, "1", "2"]


方法二


法一是将原数组中的元素和结果数组中的元素一一比较,我们可以换个思路,将原数组中重复元素的最后一个元素放入结果数组中。


function unique(a) {

  var res = [];

 

  for (var i = 0, len = a.length; i < len; i++) {

    for (var j = i + 1; j < len; j++) {

      // 这一步十分巧妙

      // 如果发现相同元素

      // 则 i 自增进入下一个循环比较

      if (a[i] === a[j])

        j = ++i;

    }

 

    res.push(a[i]);

  }

 

  return res;

}

 

 

var a = [1, 1, '1', '2', 1];

var ans = unique(a);

console.log(ans); // => ["1", "2", 1]


虽然复杂度还是 O(n^2),但是可以看到结果不同,1 出现在了数组最后面,因为结果数组取的是元素最后一次出现的位置。


方法三(sort)


如果笔试面试时只答出了上面这样 O(n^2) 的方案,可能还不能使面试官满意,下面就来说几种进阶方案。


将数组用 sort 排序后,理论上相同的元素会被放在相邻的位置,那么比较前后位置的元素就可以了。


function unique(a) {

  return a.concat().sort().filter(function(item, pos, ary) {

    return !pos || item != ary[pos - 1];

  });

}

 

 

var a = [1, 1, 3, 2, 1, 2, 4];

var ans = unique(a);

console.log(ans); // => [1, 2, 3, 4]


但是问题又来了,1 和 "1" 会被排在一起,不同的 Object 会被排在一起,因为它们 toString() 的结果相同,所以会出现这样的错误:


var a = [1, 1, 3, 2, 1, 2, 4, '1'];

var ans = unique(a);

console.log(ans); // => [1, 2, 3, 4]


当然你完全可以针对数组中可能出现的不同类型,来写这个比较函数。不过这似乎有点麻烦。


方法四 (object)


用 JavaScript 中的 Object 对象来当做哈希表,这也是几年前笔试时的解法,跟 sort 一样,可以去重完全由 Number 基本类型组成的数组。


function unique(a) {

  var seen = {};

 

  return a.filter(function(item) {

    return seen.hasOwnProperty(item) ? false : (seen[item] = true);

  });

}

 

 

var a = [1, 1, 3, 2, 1, 2, 4];

var ans = unique(a);

console.log(ans); // => [1, 3, 2, 4]


还是和方法三一样的问题,因为 Object 的 key 值都是 String 类型,所以对于 1 和 "1" 无法分别,我们可以稍微改进下,将类型也存入 key 中。


function unique(a) {

  var ret = [];

  var hash = {};

 

  for (var i = 0, len = a.length; i < len; i++) {

    var item = a[i];

 

    var key = typeof(item) + item;

 

    if (hash[key] !== 1) {

      ret.push(item);

      hash[key] = 1;

    }

  }

 

  return ret;

}

 

 

var a = [1, 1, 3, 2, '4', 1, 2, 4, '1'];

var ans = unique(a);

console.log(ans); // => [1, 3, 2, "4", 4, "1"]


虽然解决了讨厌的 1 和 "1" 的问题,但是还有别的问题!


var a = [{name: "hanzichi"}, {age: 30}, new String(1), new Number(1)];

var ans = unique(a);

console.log(ans); // => [Object, String]


但是如果数组元素全部是基础类型的 Number 值,键值对法应该是最高效的!


方法五 (ES6)


ES6 部署了 Set 以及 Array.from 方法,太强大了!如果浏览器支持,完全可以这样:


function unique(a) {

  return Array.from(new Set(a));

}

 

var a = [{name: "hanzichi"}, {age: 30}, new String(1), new Number(1)];

var ans = unique(a);

console.log(ans); // => [Object, Object, String, Number]


_.unique


最后来看看 underscore 对此的实现方式,underscore 将此封装到了 _.unique 方法中,调用方式为 _.unique(array, [isSorted], [iteratee])。其中第一个参数是必须的,是需要去重的数组,第二个参数可选,如果数组有序,则可以传入布尔值 true,第三个参数可选,如果需要对数组迭代的结果去重,则可以传入一个迭代函数。而数组元素去重是基于 === 运算符的。


其实很简单,underscore 中的实现方式和上面的方法一相似。


我们来看它的核心代码:


for (var i = 0, length = getLength(array); i  length; i++) {

  var value = array[i],

      // 如果指定了迭代函数

      // 则对数组每一个元素进行迭代

      computed = iteratee ? iteratee(value, i, array) : value;

 

  // 如果是有序数组,则当前元素只需跟上一个元素对比即可

  // 用 seen 变量保存上一个元素

  if (isSorted) {

    // 如果 i === 0,则直接 push

    // 否则比较当前元素是否和前一个元素相等

    if (!i || seen !== computed) result.push(value);

    // seen 保存当前元素,供下一次对比

    seen = computed;

  } else if (iteratee) {

    // 如果 seen[] 中没有 computed 这个元素值

    if (!_.contains(seen, computed)) {

      seen.push(computed);

      result.push(value);

    }

  } else if (!_.contains(result, value)) {  

    // 如果不用经过迭代函数计算,也就不用 seen[] 变量了

    result.push(value);

  }

}


外面的循环遍历数组元素,对于每个元素,如果数组有序,则和前一个元素比较,如果相同,则已经出现过,不加入到结果数组中,否则则加入。而如果有迭代函数,则计算传入迭代函数后的值,对值去重,调用 .contains 方法,而该方法的核心就是调用 .indexOf 方法,和我们上面说的方法一异曲同工。


关于 _.unique 方法的详细代码,可以参考 https://github.com/hanzichi/underscore-analysis/blob/master/underscore-1.8.3.js/src/underscore-1.8.3.js#L519-L547


Read More


  • 数组去重 – JS Tips – A JS tip per day!

  • Remove Duplicates from JavaScript Array

  • 从 JavaScript 数组去重谈性能优化



专栏作者简介 ( 点击 → 加入专栏作者 


韩子迟:a JavaScript beginner

打赏支持作者写出更多好文章,谢谢!



【今日微信公号推荐↓】

更多推荐请看值得关注的技术和设计公众号


其中推荐了包括技术设计极客 和 IT相亲相关的热门公众号。技术涵盖:Python、Web前端、Java、安卓、iOS、PHP、C/C++、.NET、Linux、数据库、运维、大数据、算法、IT职场等。点击《值得关注的技术和设计公众号》,发现精彩!


 
前端大全 更多文章 详解Javascript中的Object对象 结合个人经历总结的前端入门方法 前端不为人知的一面–前端冷知识集锦 一份优秀的前端开发工程师简历是怎么样的? 浅谈Web缓存
猜您喜欢 一位电商数据分析师的经验总结。[独白] python网络爬虫(三) Android 屏幕适配 【直播预告】荧火:手把手教你做有意思的设计 VisuAlgo:通过动画学习算法和数据结构