在 JS 中，数组是最常使用的一种数据存储机构之一。

1. 数组去重

去掉数组中重复的项，通过操作原有数组或者新建一个数组来实现数组是否改变。

  • 循环
  • 对象属性
  • ES6 Set

封装的函数一般使用函数名：distinct 或者 unique

1.1 循环

（1）双循环
思路：

  • 依次拿出数组中的每一项（排除最后一项，最后一项后面没有需要比较的内容了）
  • 将当前拿出项和后面的每一项依次比较
  • 如果发现重复的，我们把这个重复项从原数组中删除掉（splice）
  1. // i =  arr.length - 1 不用拿最后一项 
  2. for (var i = 0; i < array.length - 1; i++) {
  3.   var item = array[i];
  4.   //=> 和当前项后面的每一项作比较，起始索引应该是 i + 1
  5.   for (var j = i + 1; j < array.length; j++) {
  6.     if (item === array[j]) {
  7.       //=> 相等则重复，删除该项
  8.       array.splice(j, 1);
  9.       //=> 这样做会导致数组塌陷问题：当我们删除一项时，后面的项的索引会向前进一位，原有数组的索引发生改变
  10.       // 此时 j 继续累加的结果会跳过一位
  11.       j--; //=> 防止累加后跳过一位
  12.     }
  13.   }
  14. }

缺点：由于是双循环，那么循环次数将呈指数增长，数组越大时，消耗性能剧增

  1. //=> 不改变原来的数组
  2. function removeRep(arr) {
  3.   var ary = arr.slice();
  4.   // var ary = arr.slice(0);
  5.   // var ary = [].concat(arr);
  6.   for(var i = 0; i < ary.length;i++){
  7.     //确定循环用的轮数
  8.     for(var j = i+1; j < ary.length; j++){
  9.        //ary[i] 本轮的当前项
  10.        if(ary[i] == ary[j]){
  11.            ary.splice(j,1);
  12.            j--;
  13.         }
  14.      }
  15.    }
  16.    return ary;
  17. }

（2）单循环实现

  1. function removeRep2(arr) {
  2.     //利用一个额外的数组存储不重复的项
  3.     var ary = [];
  4.     for(var i = 0; i < arr.length; i++){
  5.         if(ary.indexOf(arr[i]) == -1){
  6.             ary.push(arr[i])
  7.         }
  8.     }
  9.     return ary;
  10. }

1.2 对象属性

基于对象的属性名不能重复，实现高性能的数组去重

  • 创建一个空对象
  • 依次遍历数组中的每一项，把每一项存储的值，当作对象的属性名和属性值存储起来
  1. function unique(ary) {
  2.   var obj = {};
  3.   for (var i = 0; i < ary.length; i++) {
  4.     var item = ary[i];
  5.     //=> 存储之前需要做判断：
  6.     // 如果对象中已经存在这个属性，说明当前 item 在之前出现过，也就是当前项重复，我们把当前项删除
  7.     if (typeof obj[item] !== 'undefined') {
  8.     //=> 判断可以使用 hasOwnProperty
  10.     // ary.splice(i, 1);
  11.     // i--;//=> 防止数组塌陷
  12.     //=> 这种删除方式不好，如果数组很长，我们删除某一项。
  13.     // 后面的索引都需要重新计算，非常消耗性能
  15.     /* 相对优化的删除（这种删除方法会改变原有数组的顺序）
  16.      * 1. 我们把数组最后一项的结果获取到，替换当前内容
  17.      * 2. 再把数组的最后一项删除
  18.      */
  19.       ary[i] = ary[ary.length - 1];
  20.       ary.length--;
  21.       i--;
  22.       continue;
  23.     }
  24.     //=> 把每一项作为对象的属性名和属性值存储进去
  25.     obj[item] = array[i];
  26.   }
  27. }

更简单的去重
减少判断，直接都添加进去，利用对象属性的重复覆盖特性。

  1. function removeRep3(arr) {
  2.   var obj = {},ary = [];
  3.   //=> 直接存储，重复则覆盖
  4.   for(var i = 0; i < arr.length; i++){
  5.     obj[arr[i]] = arr[i];
  6.   }
  7.   //=> 再将对象中存储的值取出
  8.   for(var k in obj){
  9.     // ary.push(k);
  10.     ary.push(obj[k])
  11.   }
  12.   return ary;
  13. }

1.3 ES6 Set 去重

利用 Set 内的元素不能重复的特性

  1. //=> Array.from 将类数组转换为数组
  2. var newArr = Array.from(new Set(arr));

1.4 包含规律对象的数组去重

实现包含对象的去重，非常难以实现，但是我们处理的数组中的数据，一般都是具有相同规律的。

下面实现的就是结构大致相同的对象数组的去重

  1. let arr = [{a:1, b:2}, {a:1, b:3}, {a:2, b:1}, {a:1, b:2}];
  2. let obj = {};
  4. for (let i = 0; i < arr.length; i++) {
  5.   let item = arr[i];
  6.   if (obj[item.a + " " + item.b]) {
  7.     arr.splice(i, 1);
  8.     i--;
  9.     continue;
  10.   }
  11.   obj[item.a + " " + item.b] = true;
  12. }

2. 数组降维

  1. var arr = [
  2.     [0,1,2,3],
  3.     [4,5,6,7],
  4.     [8,9,0,1],
  5.     [2,3,4,5]
  6. ];
  7. // 二维变成一维
  8. //=> [0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5]

一般降维都是只降一个维度。

2.1 遍历罗列

思路：

  • 建立一个新数组
  • 遍历数组中的所有二层元素，依次放入新数组中
  1. var result = [];
  2. for(var i=0;i<arr.length;i++){
  3.     for(var j=0;j<arr[i].length;j++){
  4.         result.push(arr[i][j]);
  5.     }
  6. }

2.2 使用 concat 进行拼接

思路：

  • 遍历外层数组
  • 将里层所有元素使用 concat 进行拼接为一个数组
  1. var result = [];
  2. for(var i=0;i<arr.length;i++){
  3.     result = result.concat(arr[i]);
  4. }

2.3 利用 apply 简化 concat 拼接

思路：

  • 利用 apply 传入一个数组。数组中的元素都会作为方法的参数
  • 这样就减少了外层的循环
  1. var result = [].concat.apply([],arr);

2.4 多维数组降为一维

递归

  1. Array.prototype.deepFlatten = function() {
  2.   var result = []; // 定义保存结果的数组
  3.   this.forEach(function(item) { // 遍历数组
  4.     if (Array.isArray(item)) { // 判断是否为子数组
  5.       item.forEach(arguments.callee); // 将数组拆分为每个元素，继续递归调用
  6.     } else {
  7.       result.push(item); //不为子数组则将值存入结果数组中
  8.     }
  9.   });
  10.   return result; //返回result数组
  11. }
  13. var arr = [2, 3, [2, 2],
  14.   [3, 'f', ['w', 3]], { "name": 'Tom' }
  15. ];
  16. console.log(arr.deepFlatten()); //=>[ 2, 3, 2, 2, 3, 'f', 'w', 3, { name: 'Tom' } ]

这是通过递归的方法实现了多维数组的降维，在这里面，我有使用了原型链将方法封装进了Array原型中，可以直接在数组方法中调用。

更简洁的方法：

  1. function flatten(arr) {
  2.     while(arr.some(item=>Array.isArray(item))) {
  3.     arr = [].concat(...arr);
  4.   }     
  5.   return arr;
  6. }

栈方法

这是通过栈方法，建立了一个栈，将数组的内容存进去，然后逐个取出来，如果取出来的是个数组，就将这个数组打散拼接进栈中，这样循环。

  1. Array.prototype.deepFlatten = function() {
  2.   var result = []; // 定义保存结果的数组
  3.   var stack = this; // 将数组放入栈中
  4.   while (stack.length !== 0) { // 如果栈不为空，则循环遍历
  5.     var val = stack.pop(); // 取出最后一个值
  6.     if (Array.isArray(val)) { //判断是不是数组
  7.       stack = stack.concat(val); //如果是数组就将拼接入栈中
  8.     } else {
  9.       result.unshift(val); //如果不是数组就将其取出来放入结果数组中
  10.     }
  11.   }
  12.   return result;
  13. }
  14. var arr = [2, 3, [2, 2],
  15.   [3, 'f', ['w', 3]], { "name": 'Tom' }
  16. ];
  17. console.log(arr.deepFlatten()); //=>[ 2, 3, 2, 2, 3, 'f', 'w', 3, { name: 'Tom' } ]

2.5 ES10 flat 方法

  1. [1, [2,3]].flat(2) //[1,2,3]
  3. [1, [2,3, [4,5]].flat(3) //[1,2,3,4,5]
  5. [1,[2,3, [4,5[...]].flat(Infinity) //[1,2,3,4...n]

Array.flat(n) 是ES10扁平数组的 api， n 表示维度， n 值为 Infinity 时维度为无限大。暂时不要使用。

3. 类数组转化为数组

对于类数组，可以通过转换为数组来使用原生数组的方法。

3.1 利用 slice 和 call 实现

利用 Array 的 slice 方法，克隆数组

  1. // 在 IE8 及之前版本中无效
  2. var arr = Array.prototype.slice.call(arrayLike);
  3. var arr = [].slice.call(arrayLike);

3.2 利用循环进行枚举

想要兼容 IE，只能手动枚举所有成员

  1. function convertToArray(nodes) {
  2.   var arr = null;
  3.   try {
  4.     arr = [].slice.call(nodes);
  5.   } catch (ex) {
  6.     arr = new Array();
  7.     for (var i = 0; i < nodes.length; i++) {
  8.       arr.push(nodes[i]);
  9.     }
  10.   }
  11. }

3.3 ES6 Array.form

ES6 提供了更简便的方法

  1. // ES6
  2. var arr = Array.from(arrayLike);

3.4 ES6 解构

ES6 提供的 ... 操作符

  1. var arr = [...arrayLike];

4. 数组的排序

4.1 数组的随机排序

随机打乱数组，原理：基于 sort 排序，每一次随机返回一个正数、0 或负数，来随机决定是否交换位置。最终实现随机打乱数组。

  1. ary.sort((a,b) => {
  2.   return Math.random() - 0.5;
  3. });

4.2 数组大小排序

只需要利用 sort 方法即可

  1. // 升序
  2. ary.sort((a,b) => {
  3.   return a - b; // 或者 b - a 降序
  4. });

4.3 数组最大最小值

  • 利用 Math 对象的 max 以及 min 方法
  • 通过 apply 把数组传入
  1. Math.max.apply(Math, arr);
  3. Math.max(...[1,2,3,4]);

5. 数组的合并

5.1 concat 方法

  1. [1,2,3].concat([4,5]);

5.2 ES6 解构

  1. [...[1,2,3], ...[4,5]];

5.3 利用 push 和 apply 实现

  1. [1,2,3].push.apply([4,5]);

6. 对象转化为数组

6.1 Object.keys 获取所有 key

  1. Object.keys({name: "张三", age: 14}); // ["name", "age"]

6.2 Object.values 获取所有 value

  1. Object.values({name: "张三", age: 14}); // ["张三", 14]

6.3 Object.entries 获取 key 和 value 为元组

  1. Object.entries({name: "张三", age: 14}); // [["name", "张三"], ["age", 14]]

6.4 Object.fromEntries 将元组转化为对象

  1. Object.fromEntries([["name", "张三"], ["age", 14]]); // {name: "张三", age: 14}

ES 10 的语法，暂时不要使用。

7. 扁平数组转换为层级结构数组

将后端返回的扁平的树结构数据：

  1. [
  2.   {pid: -1, name: '根目录', id: 1},
  3.   {pid: 1, name: '父目录', id: 2},
  4.   {pid: 2, name: '子目录1', id: 3},
  5.   {pid:2, name: '子目录2', id: 4}
  6. ]

转换为：

  1. [
  2.   {
  3.       pid: -1, name: '根目录', id: 1,
  4.     children: [
  5.       {
  6.           pid: 1, name: '父目录', id: 2,
  7.         children: [
  8.           {
  9.               pid: 2, name: '子目录1', id: 3,
  10.             childre: []
  11.           },
  12.           {
  13.               pid:2, name: '子目录2', id: 4,
  14.             children: []
  15.           }
  16.         ]
  17.       }
  18.     ]
  19.   }
  20. ]

实现：

  1. const getTreeList = menuList => {
  2.   let menu = []; // 用来渲染菜单的
  3.   let routeMap = {};
  4.   menuList.forEach(m => {
  5.     m.children = []; // 增加一个孩子列表
  6.     routeMap[m.id] =m ;
  7.     if(m.pid == -1){ // 是根节点
  8.       menu.push(m);
  9.     }else{
  10.       if(routeMap[m.pid]){ //找到对应的父亲 将值 塞进去
  11.         routeMap[m.pid].children.push(m);
  12.       }
  13.     }
  14.   });
  15.   return menu
  16. };