对象数组进行全键深比较去重，有什么复杂度较低的方法？

Question

例如：

let arr = [
    {a: 1, b: 2},
    {b: 2, a: 1},
    {a: 1, b: 2, c: {a: 1, b: 2}},
    {b: 2, a: 1, c: {b: 2, a: 1}}
]

要求对象比较是全键比较，不是基于某个键，而且是深度比较。

Answer 1

要实现对象数组进行全键深度比较去重，可以考虑使用以下方法：

1. 使用JSON.stringify将对象转换为字符串，然后比较字符串。注意，这种方法有一个局限性，就是对象的属性顺序必须一致，否则相同的对象可能会被视为不同。
2. 使用递归函数进行深度比较。
   以下是一个示例，实现了一个deepEqual函数进行对象的深度比较和一个uniqueArray函数进行对象数组去重：

function deepEqual(obj1, obj2) {
  if (obj1 === obj2) return true;

  if (typeof obj1 !== "object" || typeof obj2 !== "object" || obj1 === null || obj2 === null) {
    return false;
  }

  const keys1 = Object.keys(obj1);
  const keys2 = Object.keys(obj2);

  if (keys1.length !== keys2.length) return false;

  for (const key of keys1) {
    if (!keys2.includes(key)) return false;
    if (!deepEqual(obj1[key], obj2[key])) return false;
  }

  return true;
}

function uniqueArray(arr) {
  return arr.filter((item, index) => {
    return index === arr.findIndex(other => deepEqual(item, other));
  });
}

let arr = [
  { a: 1, b: 2 },
  { b: 2, a: 1 },
  { a: 1, b: 2, c: { a: 1, b: 2 } },
  { b: 2, a: 1, c: { b: 2, a: 1 } }
];

const uniqueArr = uniqueArray(arr);
console.log(uniqueArr);

在这个示例中，我们首先实现了一个deepEqual函数用于比较两个对象是否相等。然后，我们使用uniqueArray函数来过滤数组，保留唯一的对象。这个方法的时间复杂度是O(n^2)，其中n是数组的长度。这个方法在处理小型数据集时表现良好，但在处理大型数据集时可能效率较低。

如果对象的属性顺序保持一致，可以考虑使用以下方法：

function uniqueArray(arr) {
  const seen = new Set();
  return arr.filter((item) => {
    const strItem = JSON.stringify(item);
    if (seen.has(strItem)) return false;
    seen.add(strItem);
    return true;
  });
}

这种方法将对象转换为字符串，并使用Set来存储已经处理过的字符串。这种方法的时间复杂度是O(n)，其中n是数组的长度。这种方法在处理大型数据集时效率较高，但需要确保对象的属性顺序一致。

Answer 2

可以使用lodash 的 isEqual() 函数
_.isEqual({a: 1, b: 2}, {b: 2, a: 1})

Answer 3

深比较没有复杂度比较低的办法，必须 dfs 深度遍历