乐趣区

Javascrip多维数组去重深度

jiezi

昨天跟着徒弟一起面试，结果发现有些题目自己回答的也很差，没有对于某类问题做一些有深度和发散性的思考，只是表面化的“我知道”而已，我觉得我在第三层，实际我只在第一层，第一时间只能想到一些简单的办法来解决，而没有思考当题目未限定条件时会产生的异常。今天花了一些时间来做了个反思，并针对该问题的解决办法进行挖掘，希望能对自己有所提升，也能对大家有点帮助。OK，起飞~

问题描述：Javascript 数组去重

问题思考 1：实际在日常使用的时候第一时间会想到的最简单的办法是使用 ES6 的集合 set 来实现，毕竟互异 + 无序就是集合的基本特征，这个是最基础的，实践出真知：


let arr1 = [1, 2, 2, 1, 4, 5];
let set1 = new Set(arr1);
console.log(set1);
// output: Set {1, 2, 4, 5}
let w = Symbol("w");

let arr2 = [1, 1, 2, "3", 3, "3", w, w, null, null, undefined, undefined, true, true];
let set2 = new Set(arr2);
console.log(set2);
// output: Set {1, 2, '3', 3, Symbol(w), null, undefined, true }

从结果看来，这个方法可以应付日常使用的基本数据类型，也就是：String/Number/Boolean/Symbol/undefined 这几种，但是 JS 的数据类型不止有基本数据类型

问题思考 2：但是如果数组中有 object/function/array 为元素的时候会是什么样的结果呢，实践出真知：



let arr3 = [{a: 0}, {a: 0}];
let set3 = new Set(arr3);
console.log(set3);
// output: Set {{ a: 0}, {a: 0} }


let f = function() {console.log(1);};
let f1 = new f();
let f2 = new f();
let arr4 = [f1, f2];
let set4 = new Set(arr4);
console.log(set4);
// output: Set {f {}, f {}}

let arr5 = [[1, 2], [1, 2]];
let set5 = new Set(arr5);
console.log(set5);
// output: Set {[ 1, 2], [1, 2] }

实际可以看到，这个方法并不能很好的支持对象、数组类型，当内容相同的 object/function/array 类型的数据出现时，就会无法实现真正的去重功能，而实际当数组的元素为数组 / 对象的时候，其实数组已经在维度上发生了变化，而问题的深度也悄悄发生了一些变化，已经不再是一维数组的问题了，如果在这个情况下再想解决去重问题，我们就要针对不同类型进行处理了

最终思考：这个问题单纯去做发散性思考的话，是比较复杂的，且很容易在脑子里打结，实际我们根据目标来划分的话，就比较容易实现了，真正重要的是思考的过程，首先我们要思考我们要做的事情，也就是两个步骤：目标原子化，搞定原子。其实不止这个问题，无论什么问题，我们按照这个思路去解决问题，就会发现问题并没有想的那么难。

原子化：需求首先是去重，要求是能适配 Javascript 各种数据类型，所以需要的就是去重 + 判断（基本数据类型 + 引用类型）是否相等。

实现整体去重：



/**
 * 步骤
 * 1. 结果数组
 * 2. 原数组元素与结果数组中的比较
 * 3. 比较对象类型（包含数组）* 4. 比较函数类型
 * @param {Array} targetArr the target array need to unique
 * @returns {Array} result array
 */
function unique(targetArr) {console.log("unique targetArr:", targetArr);
    if (targetArr.length === 0) {return "no element!";}
    let type;
    let resultArr = [targetArr[0]];
    let elementI;
    
    for (let i = 0; i < targetArr.length; i++) {elementI = targetArr[i];
        type = typeof elementI;
        switch (type) {
            case "function":
                for (let k = 0; k < resultArr.length; k++) {if (typeof resultArr[k] === "function") {if(equalFun(elementI, resultArr[k])) {break;}
                    }
                    if (k === resultArr.length - 1) {resultArr.push(elementI);
                    }
                }

                break;
            case "object":
                for (let j = 0; j < resultArr.length; j++) {if (typeof resultArr[j] === "object") {if (equalObj(resultArr[j], elementI)) {break;}
                    }
                    if (j === resultArr.length - 1) {resultArr.push(elementI);
                    }
                }
                break;
            default:
                if (resultArr.indexOf(elementI) < 0) {resultArr.push(elementI);
                }
                break;
        }
    }
    console.log("result array: -----\n", resultArr);
    
    return resultArr;
}

实现对比函数是否相等 

function equalFun(fun1, fun2) {console.log("equalFun");
    
    return fun1.toString() === fun2.toString();
}

实现比较对象是否相等 


function equalObj(obj1, obj2) {console.log("equalObj", obj1, obj2);
    let propsArr1 = Object.getOwnPropertyNames(obj1);
    let propsArr2 = Object.getOwnPropertyNames(obj2);
    if (obj1.constructor !== obj2.constructor) {return false;}
    if (propsArr1.length !== propsArr2.length) {return false;}
    if (obj1 instanceof Array && obj2 instanceof Array) {return equalArr(obj1, obj2);
    }
    for (const p in obj1) {if (!obj2.hasOwnProperty(p)) {return false;}
        if (obj1[p] instanceof Array && obj2[p] instanceof Array) {let arr1 = obj1[p];
            let arr2 = obj2[p];
            if (!equalArr(arr1, arr2)) {return false;}
        }
        let pType1 = typeof obj1[p];
        let pType2 = typeof obj2[p];
        if (pType1 !== pType2) {return false;}
        if (pType1 === "object") {if (!equalObj(obj1[p], obj2[p])) {return false;};
        }
        if (pType1 === "function") {if (!equalFun(obj1[p], obj2[p])) {return false;}
        }
    }
    return true;
}

实现比较数组是否相等 


function equalArr(arr1, arr2) {console.log("equalArr:", arr1, arr2);
    
    if (arr1.length !== arr2.length) {return false;}
    for (let i = 0; i < arr1.length; i++) {let elementI = arr1[i];
        let iType = typeof arr1[i];
        switch (iType) {
            case "object":
                for (let j = 0; j < arr2.length; j++) {if (typeof arr2[j] === "object") {return equalObj(arr1[i], arr2[j]);
                    }
                }
                break;
            case "function":
                for (let j = 0; j < arr2.length; j++) {if (typeof arr2[j] === "function") {return equalFun(arr2[j], elementI);
                    }
                }
                break;
            default:
                if (arr2.indexOf(elementI) < 0) {return false;}
                break;
        }
    }
    // return array.toString() === array1.toString();
}

基本到这就实现了全部的去重部分的代码，如发现缺陷，请评论告知~ 非常感谢！
全部代码：

// ------ 第二题：实现数组去重
/**
 * 几点思考：* 1. 如果数组中有元素是对象呢？* 2. 如果数组中有元素是 function 呢？* 3. a = {a:0}; b = {a:0}  a === b 吗？* 4. 如果数组中有数组呢？（数组维度）* 
 * @param {Array} targetArr the target array need to unique
 * @returns {Array} result array
 */
function unique(targetArr) {console.log("unique targetArr:", targetArr);
    if (targetArr.length === 0) {return "no element!";}
    let type;
    let resultArr = [targetArr[0]];
    let elementI;
    
    for (let i = 0; i < targetArr.length; i++) {elementI = targetArr[i];
        type = typeof elementI;
        switch (type) {
            case "function":
                for (let k = 0; k < resultArr.length; k++) {if (typeof resultArr[k] === "function") {if(equalFun(elementI, resultArr[k])) {break;}
                    }
                    if (k === resultArr.length - 1) {resultArr.push(elementI);
                    }
                }

                break;
            case "object":
                for (let j = 0; j < resultArr.length; j++) {if (typeof resultArr[j] === "object") {if (equalObj(resultArr[j], elementI)) {break;}
                    }
                    if (j === resultArr.length - 1) {resultArr.push(elementI);
                    }
                }
                break;
            default:
                if (resultArr.indexOf(elementI) < 0) {resultArr.push(elementI);
                }
                break;
        }
    }
    console.log("result array: -----\n", resultArr);
    
    return resultArr;
}

function equalFun(fun1, fun2) {console.log("equalFun");
    
    return fun1.toString() === fun2.toString();
}

function equalObj(obj1, obj2) {console.log("equalObj", obj1, obj2);
    let propsArr1 = Object.getOwnPropertyNames(obj1);
    let propsArr2 = Object.getOwnPropertyNames(obj2);
    if (obj1.constructor !== obj2.constructor) {return false;}
    if (propsArr1.length !== propsArr2.length) {return false;}
    if (obj1 instanceof Array && obj2 instanceof Array) {return equalArr(obj1, obj2);
    }
    for (const p in obj1) {if (!obj2.hasOwnProperty(p)) {return false;}
        let pType1 = typeof obj1[p];
        let pType2 = typeof obj2[p];
        if (pType1 !== pType2) {return false;}
        if (pType1 === "object") {if (!equalObj(obj1[p], obj2[p])) {return false;};
        }
        if (pType1 === "function") {if (!equalFun(obj1[p], obj2[p])) {return false;}
        }
        if (obj1[p] instanceof Array && obj2[p] instanceof Array) {let arr1 = obj1[p];
            let arr2 = obj2[p];
            if (!equalArr(arr1, arr2)) {return false;}
        }
    }
    return true;
}

function equalArr(arr1, arr2) {console.log("equalArr:", arr1, arr2);
    
    if (arr1.length !== arr2.length) {return false;}
    for (let i = 0; i < arr1.length; i++) {let elementI = arr1[i];
        let iType = typeof arr1[i];
        switch (iType) {
            case "object":
                for (let j = 0; j < arr2.length; j++) {if (typeof arr2[j] === "object") {return equalObj(arr1[i], arr2[j]);
                    }
                }
                break;
            case "function":
                for (let j = 0; j < arr2.length; j++) {if (typeof arr2[j] === "function") {return equalFun(arr2[j], elementI);
                    }
                }
                break;
            default:
                if (arr2.indexOf(elementI) < 0) {return false;}
                break;
        }
    }
    return true;
}
退出移动版