Skip to content

Latest commit

 

History

History
127 lines (91 loc) · 3.95 KB

File metadata and controls

127 lines (91 loc) · 3.95 KB

English Version

题目描述

给定两个对象 o1o2 ,请你检查它们是否 完全相等

对于两个 完全相等 的对象,它们必须包含相同的键,并且相关的值也必须 完全相等 。如果两个对象通过了 === 相等性检查,它们也被认为是 完全相等 的。

你可以假设这两个对象都是 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 <= 105
  • 1 <= JSON.stringify(o2).length <= 105
  • maxNestingDepth <= 1000

解法

方法一:递归

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

否则,我们判断 o1o2 的类型是否相同。如果不同,则返回 false

接下来,我们判断 o1o2 是否都是数组。如果不是,则返回 false

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

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

时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$o1o2 的长度。

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;
    }
}

...