数组扁平化、去重、排序

题目描述

已知一个数组 var arr = [[1, 3, 2, 1],[5, 3, 4, 8, 5, 6, 5],[6, 2, 8, 9, [4, 11, 15, 8, 9, 12, [12, 13, [10], 14]]], 16]，用 js 编写一个程序将这个数组扁平化，并得到一个升序且无重复值的数组。得到最终结果为：[1,2,3,4,5,6,8,9,10,11,12,13,14,15,16]。

参考：https://www.jb51.net/article/181192.htm

1. 数组扁平化

var arr = [[1, 3, 2, 1],
[5, 3, 4, 8, 5, 6, 5],
[6, 2, 8, 9, [4, 11, 15, 8, 9, 12, [12, 13, [10], 14]]], 
16]

1.1 方法1：toString

注意：如果 arr 数组中有空数组，不使用此方法，用下面的方法；同时得到数组的值是字符串，不是数字

var newArr = arr.toString().split(',') // 0: "1", "3", "2", "1", "5", "3", "4", "8", "5", "6", "5", "6", "2", "8", "9", "4", "11", "15", "8", "9", "12", "12", "13", "10", "14", "16"

1.2 方法2：正则表达式

var newArr1 = JSON.parse("[" +JSON.stringify(arr).replace(/(\[\]\,)|[\[\]]*/g, "") + "]");// [1, 3, 2, 1, 5, 3, 4, 8, 5, 6, 5, 6, 2, 8, 9, 4, 11, 15, 8, 9, 12, 12, 13, 10, 14, 16]

1.3 方法3：reduce

reduce() 方法对累加器和数组中的每个元素 (从左到右)应用一个函数，将其减少为单个值，reduce详细介绍

function flatten(arr) {
    return arr.reduce((a, b) => [].concat(
        Array.isArray(a) && a ? flatten(a) : a,         
        Array.isArray(b) && b ? flatten(b) : b), 
        []
    )
 }
var newArr2 = flatten(arr)
// [1, 3, 2, 1, 5, 3, 4, 8, 5, 6, 5, 6, 2, 8, 9, 4, 11, 15, 8, 9, 12, 12, 13, 10, 14, 16]

1.4 遍历数组

var newArr3 = []
function flat(arr) {
    for(var i = 0; i < arr.length; i++) {
        if(arr[i] instanceof Array) {
            flat(arr[i])
        } else {
            newArr3.push(arr[i])
        }
    }
}
flat(arr)

2. 数组去重

2.1 方法1：Set

Array.from方法用于将两类对象转为真正的数组：类似数组的对象（array-like object）和可遍历（iterable）的对象（包括ES6新增的数据结构Set和Map）。
ES6 提供了新的数据结构 Set。它类似于数组，但是成员的值都是唯一的，没有重复的值；Set详细介绍

var duplicate = Array.from(new Set(newArr1))

2.2 方法2：reduce

通过数组reduce方法，利用indexOf判断上一次回调返回数组a中是否包含当前元素b的索引，如果不存在，则把b元素加入a数组，否则直接返回a。

var duplicate1 = newArr1.reduce((a, b) => {
  if(a.indexOf(b) === -1) {
    a.push(b)
  }
  return a
}, [])

2.3 方法3：数组下标去重

通过数组的过滤filter方法，利用indexOf获取当前元素ele在被过滤数组farr中的第一个索引值，如果值与当前索引值index相等则返回，如果不相等则过滤。

var duplicate2 = newArr1.filter((ele, index, farr) => {
  return farr.indexOf(ele) === index
})

2.4 方法4：遍历数组

遍历数组，建立新duplicate3 数组，利用indexOf判断元素是否存在于duplicate3 新数组中，不存在则push到duplicate3 新数组。

var duplicate3 = []
for(var i = 0; i < newArr1.length; i++) {
  if(duplicate3.indexOf(newArr1[i]) === -1) {
    duplicate3.push(newArr1[i])
  }
}

2.5 方法5：排序后相邻去重法

给传入数组排序，排序后相同值相邻，然后遍历时新数组只加入不与前一值重复的值。

function unique3(arr) {
  arr.sort();
  var newArr = [arr[0]];
  for(var i = 1, len = arr.length; i < len; i++) {
    if(arr[i] !== newArr[newArr.length - 1]) {
      newArr.push(arr[i]);
    }
  }
  return newArr;
}
var duplicate4 = unique3(newArr1)

3. 数组排序

var duplicate=[1, 3, 2, 5, 4, 8, 6, 9, 11, 15, 12, 13, 10, 14, 16]

3.1 方法1：sort

function systemSort(arr) {
  return arr.sort(function(a, b) {
    return a - b
  })
}
var sort = systemSort(duplicate)

3.2 方法2：冒泡

 function bubbleSort(arr) {
  var len=arr.length
    for(var i = len-1; i > 0; i--) {
     for(var j = 0; j < i; j++) {
       if(arr[j] > arr[j+1]) {
       var tmp = arr[j]
       arr[j] = arr[j + 1]
       arr[j + 1]= tmp
       } 
     }
    }
    return arr
  }
  var sort1 = bubbleSort(duplicate)

3.3 方法3：插入

function insertSort(arr){
  var tmp
  for(var i = 1; i < arr.length; i++) {
   tmp = arr[i]
   for(var j = i; j >= 0; j--) {
    if(arr[j - 1] > tmp) {
     arr[j] = arr[j - 1];
    } else {
     arr[j] = tmp;
     break;
    }
   }
  }
  return arr
}
var sort2 = insertSort(duplicate)

排序方法还有很多，这里不进行一一总结，可以参考前端面试必备——基本排序算法

算法文章被收录于专栏

JavaScript算法