去除数组重复项.md

去除数组重复项

实现一个函数，去除数组中重复的项，数组中的所有的项都是对象，对象的所有的值的类型需要相同才是重复的，需要实现复杂度为O(n)

首先实现一个 O(n^3)的，最符合直觉的

const unique = function (arrs) {
    let duplicates = [];
    for (let i = 0; i < arrs.length; i++) {
        for (let j = i + 1; j < arrs.length; j++) {
            if (isEqual(arrs[i], arrs[j]) && duplicates.indexOf(j) === -1) {
                duplicates.push(j);
            }
        }
    }

    // 然后再做一次循环，把 arrs 中含有 duplicates 中的索引删除掉
    for (let i = duplicates.length - 1; i >= 0; i--) {
        arrs.splice(i, 1);
    }

    return arrs;
}

// 用来判断对象是否相等
function isEqual(a, b) {
    let aKeys = Object.keys(a);
    let bKeys = Object.keys(b);
    if (aKeys.length !== bKeys.length) {
        return false;
    }

    aKeys.sort((c, d) => c - d || c.localeCompare(d));
    bKeys.sort((c, d) => c - d || c.localeCompare(d));

    for (let i = 0; i < aKeys.length; i++) {
        if (a[aKeys[i]] !== b[bKeys[i]]) {
            return false;
        }
    }

    return true;
}

要实现 O(n^2) 所以就只能循环一次，所以就只能上指针了 感觉这个应该算是 n，毕竟在对象中的key 循环和数组的循环，不是同一个n，对象中 key 循环的复杂度可以算作是常数阶 所以下面这个的复杂度可以算作是O(n)

const unique = function (arrs) {
    let duplicates = [];
    let i = 0;
    let j = i + 1;
    while (i < arrs.length - 1) {
        // isEqual 用上面那个函数的
        if (isEqual(arrs[i], arrs[j]) && duplicates.indexOf(j) === -1) {
            duplicates.push(j);
        }
        // 每次通过 j++ 来重复上面的条件判断
        j++;
        // 通过 j 等于数组的长度，知道当前i情况下，已经比较完了，然后来重置 i 和 j，开始下一轮比较
        if (j === arrs.length) {
            i++;
            j = i + 1;
        }
    }
    // 然后再做一次循环，把 arrs 中含有 duplicates 中的索引删除掉
    for (let i = duplicates.length - 1; i >= 0; i--) {
        arrs.splice(i, 1);
    }

    return arrs;
}

测试

let arrs = [
    {
        a: 1,
        b: 2
    },
    {
        b: 2,
        a: '1'
    },
    {
        b: 2,
        a: 1
    },
    {
        c: 3
    },
    {
        d: 4
    }
];
let result = unique(arrs);
console.log(result);