New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

JavaScript 数组去重 #9

Open
hanzichi opened this Issue Jun 5, 2016 · 20 comments

Comments

Projects
None yet
@hanzichi
Owner

hanzichi commented Jun 5, 2016

Why underscore

(觉得这部分眼熟的可以直接跳到下一段了...)

最近开始看 underscore.js 源码,并将 underscore.js 源码解读 放在了我的 2016 计划中。

阅读一些著名框架类库的源码,就好像和一个个大师对话,你会学到很多。为什么是 underscore?最主要的原因是 underscore 简短精悍(约 1.5k 行),封装了 100 多个有用的方法,耦合度低,非常适合逐个方法阅读,适合楼主这样的 JavaScript 初学者。从中,你不仅可以学到用 void 0 代替 undefined 避免 undefined 被重写等一些小技巧 ,也可以学到变量类型判断、函数节流&函数去抖等常用的方法,还可以学到很多浏览器兼容的 hack,更可以学到作者的整体设计思路以及 API 设计的原理(向后兼容)。

之后楼主会写一系列的文章跟大家分享在源码阅读中学习到的知识。

欢迎围观~ (如果有兴趣,欢迎 star & watch~)您的关注是楼主继续写作的动力

数组去重

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

数组去重,一般需求是给你一个数组,调用去重方法,返回数值副本,副本中没有重复元素。一般来说,两个元素通过 === 比较返回 true 的视为相同元素,需要去重,所以,1"1" 是不同的元素,1new 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

@idda

This comment has been minimized.

idda commented Jun 22, 2016

学习了

@silasFFF

This comment has been minimized.

silasFFF commented Jul 5, 2016

1024

@L9m

This comment has been minimized.

L9m commented Aug 28, 2016

学习了

@Wangbaogang

This comment has been minimized.

Wangbaogang commented Oct 19, 2016

赞赞赞
-- 来自点赞小能手

@luoliqiang luoliqiang referenced this issue Feb 9, 2017

Open

文章1 #1

@aleen42

This comment has been minimized.

aleen42 commented Feb 20, 2017

方法三如果用严格判定 item !== arr[pos - 1] 的话,不就能解决 Number 与 String 排在一起的问题咯?

@BigKongfuPanda

This comment has been minimized.

BigKongfuPanda commented Feb 23, 2017

厉害,没想到有这么多种方法呢

@BigKongfuPanda

This comment has been minimized.

BigKongfuPanda commented Feb 23, 2017

我想咨询一个问题,如果说数组是这样:arr = [{name:"tom"},{name:"tom"},{age: 18}]; 请问数组中的第一项和第二项,是算重复的嘛? 如果是的话,你上面的方法好像失效了。

@aleen42

This comment has been minimized.

aleen42 commented Feb 24, 2017

@BigKongfuPanda 在作者看来,这种情况应该属于引用不同,因此不能称作完全相同的两个元素。这在于你如何理解两个元素何谓重复。

@BigKongfuPanda

This comment has been minimized.

BigKongfuPanda commented Feb 24, 2017

@tiansn

This comment has been minimized.

tiansn commented Feb 27, 2017

@hanzichi ,能分析下,每种方法的复杂度么,特别是最后的那几种

@zhangbowei

This comment has been minimized.

zhangbowei commented Mar 1, 2017

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

var a = [{name: "hanzichi"}, {name: "hanzichi"},{age: 30}, new String(1), new Number(1)];
var ans = unique(a);
console.log(JSON.stringify(ans));
//output
[{"name":"hanzichi"},{"name":"hanzichi"},{"age":30},"1",1]

@JasonWilltrue

This comment has been minimized.

JasonWilltrue commented Mar 8, 2017

学习了

1 similar comment
@Hal-pan

This comment has been minimized.

Hal-pan commented Mar 10, 2017

学习了

@CatBone

This comment has been minimized.

CatBone commented Mar 15, 2017

还一种简单的,可以运用es6的扩展运算符
var unique = a => [...new Set(a)]

😝😝😝

@HowardTangHw

This comment has been minimized.

HowardTangHw commented Aug 15, 2017

您好,我有个疑问,为什么在方法2中j=++i会把外部的循环中断掉,而不执行语句res.push(a[i])呢?

function unique(a) {
  var res = [];

  for (var i = 0, len = a.length; i < len; i++) {
    for (var j = i + 1; j < len; j++) {
      if (a[i] === a[j]) {
        console.log('中断了')
        j = ++i;
      }
    }
    // 不清楚为啥j=++i;会break掉循环,不进入这一步
    console.log('没被中断');
    res.push(a[i]);
  }

  return res;
}

var a = [1, 1, "1", "2", 1];
var ans = unique(a);
console.log(ans); // => ["1", "2", 1]
@Arvinzhu

This comment has been minimized.

Arvinzhu commented Sep 18, 2017

@HowardTangHw 没有中断外部循环,而是内部循环在遇到充负的元素时,修改i的值,也就是修改外部循环下次循环的起点,当内部循环执行完毕后,push一个没有重复的值到res中,然后外部循环执行 以修改后的i值执行i++开始执行下一次循环

@seaskymonster

This comment has been minimized.

seaskymonster commented Sep 20, 2017

对于 1 和 "1" 无法分别这个问题:

其实可以在你的方法四上直接改
function unique(a) { var seen = {}; return a.filter(function(item){ return seen.hasOwnProperty(typeof(item)+item) ? false: (seen[typeof(item)+item] = true); }) }

@isLishude

This comment has been minimized.

isLishude commented Sep 21, 2017

indexOf 最大的问题就是 NaN 无法去重

@anotherleon

This comment has been minimized.

anotherleon commented Mar 28, 2018

方法三: return !pos || item != ary[pos - 1]; 换成 return !pos || item !== ary[pos - 1]; 使用严格相等应该就行了吧

@anotherleon

This comment has been minimized.

anotherleon commented Mar 28, 2018

_20180328161606

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment