深度相等

指令

编写一个函数，接收两个任意类型的参数。该函数应执行深度相等检查。

输入：任意类型，任意类型
输出：布尔值

提示

• 深度相等用于检查对象和数组之间的等价性。由于 JavaScript 中的值与引用概念，相等运算符（==、===）无法满足需求。对于两个不同的数组或对象，即使它们包含相同的元素，这些运算符也会返回 false。

• 如果比较的是对象或数组，需要深入其中，检查每个元素是否相同。如果某个元素本身也是数组或对象，则需要继续深入检查。

• 对象或数组可能嵌套多层。我们的函数必须递归地深入到每一层。

• 本题考察多个 JavaScript 概念：

  • 值与引用的区别
  • 不同数据类型（如 NaN 和 null）的特殊行为
  • 使用 typeof
  • 代码复用能力

---

1function deepEquals(a, b) {
2    // 你的代码在这里
3}

---

解答

这个问题包含多个部分，我们来逐步逻辑分析。

1. 使用 == 或 === 比较 NaN 与 NaN 时，结果总是 false。因此，我们需要首先判断两个输入是否都是 NaN。

2. 如果两个值类型不同，可以直接返回 false。

3. 如果类型相同且不是对象，可以直接使用 === 进行相等比较。需要注意的是，null 的 typeof 结果是 'object'，这是 JavaScript 的一个历史遗留问题。因此在判断时要特别处理 null。

4. 必须确保两个对象拥有相同数量的属性，否则返回 false。

5. 遍历第一个对象的所有键，检查第二个对象中对应键的值是否也完全相等。

6. 所有检查通过后，返回 true。

以下是上述逻辑的伪代码：

1// 确保 a 和 b 深度相等。
2function deepEquals(a, b) {
3    // 1. 如果两者都是 NaN
4        // 返回 true
5  
6    // 2. 如果类型不同
7        // 返回 false
8  
9    // 3. 如果都不是对象，或者其中一个是 null
10        // 返回简单相等比较的结果
11    
12    // 4. 确保两个对象具有相同数量的属性。如果不是
13        // 返回 false。
14
15    // 5. 遍历对象的所有键，确保两个对象中对应的值完全一致。如果不是
16        // 返回 false。
17  
18    // 6. 返回 true。
19}

现在将伪代码转化为实际代码：

1function deepEquals(a, b) {
2    if (Number.isNaN(a) && Number.isNaN(b)) {
3        return true;
4    }
5
6    if (typeof a !== typeof b) {
7        return false;
8    }
9
10    if (typeof a !== 'object' || a === null || b === null) {
11        return a === b;
12    }
13
14    if (Object.keys(a).length !== Object.keys(b).length) {
15        return false;
16    }
17
18    for (const key in a) {
19        // 确保两个对象中对应键的值完全一致。如果不是
20            // 返回 false。
21    }
22
23    return true;
24}

最后一步是确保对象中存储的每一个值都彼此深度相等。为此，我们需要对每个属性重复前面的检查步骤。这表明我们的函数应当是递归的。

1function deepEquals(a, b) {
2    if (Number.isNaN(a) && Number.isNaN(b)) {
3        return true;
4    }
5
6    if (typeof a !== typeof b) {
7        return false;
8    }
9
10    if (typeof a !== 'object' || a === null || b === null) {
11        return a === b;
12    }
13
14    if (Object.keys(a).length !== Object.keys(b).length) {
15        return false;
16    }
17
18    for (const key of Object.keys(a)) {
19        if (!Object.prototype.hasOwnProperty.call(b, key) || !deepEquals(a[key], b[key])) {
20            return false;
21        }
22    }
23
24    return true;
25}

时间复杂度

函数需要遍历两个输入的所有属性。假设两个输入深度相等，时间复杂度为：

O(n)

空间复杂度

这是一个递归函数，调用栈的深度通常与对象大小成正比，因此：

O(n)