2628. 完全相等的 JSON 对象 🔒

难度中等

题目描述

给定两个对象 o1 和 o2 ，请你检查它们是否 完全相等 。

对于两个 完全相等 的对象，必须满足以下条件：

如果两个值都是原始类型，它们通过了 === 等式检查，则认为这两个值是 完全相等 的。
如果两个值都是数组，在它们具有相同元素且顺序相同，并且每个元素在这些条件下也 完全相等 时，认为这两个值是 完全相等 的。
如果两个值都是对象，在它们具有相同键，并且每个键关联的值在这些条件下也 完全相等 时，认为这两个值是 完全相等 的。

你可以假设这两个对象都是 JSON.parse 的输出。换句话说，它们是有效的 JSON 。

请你在不使用 lodash 的 _.isEqual() 函数的前提下解决这个问题。

示例 1：

输入：o1 = {"x":1,"y":2}, o2 = {"x":1,"y":2}
输出：true
输入：键和值完全匹配。

示例 2：

输入：o1 = {"y":2,"x":1}, o2 = {"x":1,"y":2}
输出：true
解释：尽管键的顺序不同，但它们仍然完全匹配。

示例 3：

输入：o1 = {"x":null,"L":[1,2,3]}, o2 = {"x":null,"L":["1","2","3"]}
输出：false
解释：数字数组不同于字符串数组。

示例 4：

输入：o1 = true, o2 = false
输出：false
解释：true !== false

提示：

1 <= JSON.stringify(o1).length <= 10⁵
1 <= JSON.stringify(o2).length <= 10⁵
maxNestingDepth <= 1000

解法

方法一：递归

思考

要比较任意 JSON 值，=== 只能处理基本类型，对象与数组需递归。数组与普通对象不能互等，键集合也须一致。

先处理 null 与非对象；类型或「是否为数组」不同则否。数组按下标递归，对象按键递归，长度或键数不一致即失败。

我们先判断 o1 是否为空，或者 o1 是否非对象类型。如果是，则直接返回 o1 和 o2 是否相等。

否则，我们判断 o1 和 o2 的类型是否相同。如果不同，则返回 false。

接下来，我们判断 o1 和 o2 是否都是数组。如果不是，则返回 false。

如果是数组，则判断两个数组的长度是否相同。如果不同，则返回 false。否则，我们遍历两个数组对应位置的元素，递归调用 areDeeplyEqual 函数，判断两个元素是否相等。如果有一个元素不相等，则返回 false。否则，返回 true。

如果 o1 和 o2 都不是数组，则判断两个对象的键的个数是否相同。如果不同，则返回 false。否则，我们遍历 o1 的所有键，递归调用 areDeeplyEqual 函数，判断两个键对应的值是否相等。如果有一个键对应的值不相等，则返回 false。否则，返回 true。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为 o1 和 o2 的长度。

TypeScript

function areDeeplyEqual(o1: any, o2: any): boolean {
    if (o1 === null || typeof o1 !== 'object') {
        return o1 === o2;
    }
    if (typeof o1 !== typeof o2) {
        return false;
    }
    if (Array.isArray(o1) !== Array.isArray(o2)) {
        return false;
    }
    if (Array.isArray(o1)) {
        if (o1.length !== o2.length) {
            return false;
        }
        for (let i = 0; i < o1.length; i++) {
            if (!areDeeplyEqual(o1[i], o2[i])) {
                return false;
            }
        }
        return true;
    } else {
        const keys1 = Object.keys(o1);
        const keys2 = Object.keys(o2);
        if (keys1.length !== keys2.length) {
            return false;
        }
        for (const key of keys1) {
            if (!areDeeplyEqual(o1[key], o2[key])) {
                return false;
            }
        }
        return true;
    }
}

2628. 完全相等的 JSON 对象 🔒

题目描述

解法

方法一：递归

评论