【JavaScript】数组拍平与数组去重

[swiftwind0405]

数组扁平化

数组的扁平化，就是将一个嵌套多层的数组 array (嵌套可以是任何层数)转换为只有一层的数组。也就是多维数组的降维方式。

递归

循环数组元素，如果还是一个数组，就递归调用该方法：

// 1. 递归
function flatten(arr) {    
	let result = []    
	for(let i = 0; i < arr.length; i++) {        
		if(Array.isArray(arr[i])) {            
			result = result.concat(flatten(arr[i]))        
		} else {            
			result.push(arr[i])        
		}    
	}    
	return result
}

reduce

既然是对数组进行处理，最终返回一个值，我们就可以考虑使用 reduce 来简化代码：

// 2. 借助 reduce
function flatten(arr) {    
	return arr.reduce((acc, cur) => {        
		return acc.concat(Array.isArray(cur) ? flatten(cur) : cur)    
	}, [])
}

借助 apply/call

// 3. 借助 apply/call
function flatten(arr) {    
	while(arr.some(res => Array.isArray(res))) {        
		arr = Function.apply.call([].concat, [], arr)    
	}    
	return arr
}

扩展运算符

ES6 增加了扩展运算符，用于取出参数对象的所有可遍历属性，拷贝到当前对象之中：

// 4. ES6 拓展运算符
function flatten(arr) {    
	while(arr.some(res => Array.isArray(res))) {        
		arr = [].concat(...arr)    }    
	return arr
}

ES6的flat

ES6 为数组实例新增了 flat 方法，用于将嵌套的数组“拉平”，变成一维的数组。该方法返回一个新数组，对原数组没有影响。
flat 默认只会 “拉平” 一层，如果想要 “拉平” 多层的嵌套数组，需要给 flat 传递一个整数，表示想要拉平的层数。
使用 Infinity 作为深度，展开任意深度的嵌套数组。

// 5. ES6 flat 方法
[1, 2, [3, , [4, 5]]].flat(Infinity)

数组去重

两次循环遍历

时间复杂度是O(n^2)，如果数组长度很大，那么将会非常耗费内存

直接使用for：

function unique(arr) {
    if (!Array.isArray(arr)) {
        console.log('type error!')
        return
    }
    let res = [arr[0]]
    for (let i = 1; i < arr.length; i++) {
        let flag = true
        for (let j = 0; j < res.length; j++) {
            if (arr[i] === res[j]) {
                flag = false;
                break
            }
        }
        if (flag) {
            res.push(arr[i])
        }
    }
    return res
}

使用 indexOf：

function uniq(arry) {
    var result = [];
    for (var i = 0; i < arry.length; i++) {
        if (result.indexOf(arry[i]) === -1) {
            //如 result 中没有 arry[i],则添加到数组中
            result.push(arry[i])
        }
    }
    return result;
}

使用 includes：

function uniq(arry) {
    var result = [];
    for (var i = 0; i < arry.length; i++) {
        if (!result.includes(arry[i])) {
            //如 result 中没有 arry[i],则添加到数组中
            result.push(arry[i])
        }
    }
    return result;
}

使用 reduce：
用reduce可以写的比较简洁

function uniq(arry) {
    return arry.reduce((prev, cur) => prev.includes(cur) ? prev : [...prev, cur], []);
}

排序后去重

排序后比较相邻元素，不算排序，只需要遍历一次数组

function unique(arr) {
    if (!Array.isArray(arr)) {
        console.log('type error!')
        return
    }
    arr = arr.sort()
    let res = []
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] !== arr[i-1]) {
            res.push(arr[i])
        }
    }
    return res
}

ES6的Set、Map

空间换时间的做法

使用 Set：

// 解构赋值
function uniq(arry) {
    return [...new Set(arry)];
}
// Array.from方法可以将Set结构转换为数组结果
function uniq(arry) {
    return Array.from(new Set(arry));
}

使用 Map：

function uniq(arry) {
    let map = new Map();
    let result = new Array();
    for (let i = 0; i < arry.length; i++) {
        if (map.has(arry[i])) {
            map.set(arry[i], true);
        } else {
            map.set(arry[i], false);
            result.push(arry[i]);
        }
    }
    return result;
}

参考资料

• JavaScript专题之数组扁平化 · Issue #36 · mqyqingfeng/Blog
• JavaScript专题之数组去重 · Issue #27 · mqyqingfeng/Blog