2700. 两个对象之间的差异 🔒

🟠   🔗 力扣 LeetCode

题目

Write a function that accepts two deeply nested objects or arrays obj1 and obj2 and returns a new object representing their differences.

The function should compare the properties of the two objects and identify any changes. The returned object should only contains keys where the value is different from obj1 to obj2.

For each changed key, the value should be represented as an array [obj1 value, obj2 value]. Keys that exist in one object but not in the other should not be included in the returned object. The end result should be a deeply nested object where each leaf value is a difference array.

When comparing two arrays, the indices of the arrays are considered to be their keys.

You may assume that both objects are the output of JSON.parse.

Example 1:

Input:

obj1 = {}

obj2 =

Output: {}

Explanation: There were no modifications made to obj1. New keys "a" and "b" appear in obj2, but keys that are added or removed should be ignored.

Example 2:

Input:

obj1 = { "a": 1, "v": 3, "x": [], "z": { "a": null } }

obj2 = { "a": 2, "v": 4, "x": [], "z": { "a": 2 } }

Output:

{ "a": [1, 2], "v": [3, 4], "z": { "a": [null, 2] } }

Explanation: The keys "a", "v", and "z" all had changes applied. "a" was changed from 1 to 2. "v" was changed from 3 to 4. "z" had a change applied to a child object. "z.a" was changed from null to 2.

Example 3:

Input:

obj1 =

obj2 =

Output:

{ "v": [6, 7], "z": { "2": [4, 3], "3": { "0": [2, 1] } } }

Explanation: In obj1 and obj2, the keys "v" and "z" have different assigned values. "a" is ignored because the value is unchanged. In the key "z", there is a nested array. Arrays are treated like objects where the indices are keys. There were two alterations to the the array: z[2] and z[3][0]. z[0] and z[1] were unchanged and thus not included. z[3][1] and z[3][2] were removed and thus not included.

Example 4:

Input:

obj1 = { "a": {"b": 1}, }

obj2 =

Output: { "a": [{"b": 1}, [5]] }

Explanation: The key "a" exists in both objects. Since the two associated values have different types, they are placed in the difference array.

Example 5:

Input:

obj1 = { "a": [1, 2,

obj2 = { "b": false, "a": [1, 2,

Output: {}

Explanation: Apart from a different ordering of keys, the two objects are identical so an empty object is returned.

Constraints:

• obj1 and obj2 are valid JSON objects or arrays
• 2 <= JSON.stringify(obj1).length <= 10^4
• 2 <= JSON.stringify(obj2).length <= 10^4

题目大意

请你编写一个函数，它接收两个深度嵌套的对象或数组 obj1 和 obj2 ，并返回一个新对象表示它们之间差异。

该函数应该比较这两个对象的属性，并识别任何变化。返回的对象应仅包含从 obj1 到 obj2 的值不同的键。

对于每个变化的键，值应表示为一个数组 [obj1 value, obj2 value] 。不存在于一个对象中但存在于另一个对象中的键不应包含在返回的对象中。在比较两个数组时，数组的索引被视为它们的键。最终结果应是一个深度嵌套的对象，其中每个叶子的值都是一个差异数组。

你可以假设这两个对象都是 JSON.parse 的输出结果。

提示：

• obj1 和 obj2 都是有效的 JSON 对象或数组
• 2 <= JSON.stringify(obj1).length <= 10^4
• 2 <= JSON.stringify(obj2).length <= 10^4

解题思路

1. 类型比较：

   • 首先，检查 obj1 和 obj2 的类型。如果它们的类型不同，直接返回一个包含两个对象的数组 [obj1, obj2]，这一步确保了后续的比较是基于相同类型的对象。

2. 基本数据类型比较：

   • 如果两个对象是基本数据类型（即不是对象或数组），则直接比较它们的值。
   • 如果值相等，返回一个空对象 {}，表示没有差异；
   • 如果不相等，返回一个数组 [obj1, obj2]，表示两个值的差异。

3. 对象或数组的处理：

   • 对于数组或对象，初始化一个空对象 res 用于存储差异结果。
   • 使用 Object.keys(obj1) 获取 obj1 的所有键，并过滤出同时存在于 obj2 中的公共属性 commonKeys。

4. 递归比较：

   • 对于每个公共属性，递归调用 objDiff 函数以获取子对象的差异。如果返回的差异对象 subDiff 不是空的，则将其添加到结果对象 res 中。

5. 返回结果：

   • 最终，返回结果对象 res，它包含了所有不同的键及其对应的差异值。

复杂度分析

• 时间复杂度：O(n)，其中 n 是两个对象的总键数，需要遍历对象所有的键，如果对象嵌套层级很深，递归调用的深度也会增加，但在大多数情况下，时间复杂度保持在 O(n)。
• 空间复杂度：O(n)，主要由存储差异的结果对象 res 占据，需要存储所有不同的值。

代码

/**
 * @param {Object|Array} obj1
 * @param {Object|Array} obj2
 * @return {Object}
 */
var objDiff = function (obj1, obj2) {
	// 1. 若 obj1 和 obj2 类型不同，直接返回 [obj1, obj2]
	if (type(obj1) !== type(obj2)) return [obj1, obj2];

	// 2. 若是基本数据类型，直接比较值是否相等
	if (!isObject(obj1)) return obj1 == obj2 ? {} : [obj1, obj2];

	// 3. 若是数组或对象
	let res = {};

	// 找到两个对象的公共属性
	const commonKeys = Object.keys(obj1).filter((key) => key in obj2);
	commonKeys.forEach((key) => {
		// 递归比较
		const subDiff = objDiff(obj1[key], obj2[key]);
		// 过滤掉值为空的属性
		if (Object.keys(subDiff).length) res[key] = subDiff;
	});
	return res;
};

// 返回 obj 的数据类型
function type(obj) {
	return Object.prototype.toString.call(obj).slice(8, -1);
}
// 判断 obj 是否为对象和数组
function isObject(obj) {
	return typeof obj == 'object' && obj !== null;
}

相关题目

题号	标题	题解	标签	难度	力扣
2628	完全相等的 JSON 字符串 🔒	[✓]		🟠	🀄️ 🔗
2633	将对象转换为 JSON 字符串 🔒	[✓]		🟠	🀄️ 🔗