2823. 深度对象筛选 🔒

🟠   🔗 力扣 LeetCode

题目

Given an object or an array obj and a function fn, return a filtered object or array filteredObject.

Function deepFilter should perform a deep filter operation on the obj. The deep filter operation should remove properties for which the output of the filter function fn is false, as well as any empty objects or arrays that remain after the keys have been removed.

If the deep filter operation results in an empty object or array, with no remaining properties, deepFilter should return undefined to indicate that there is no valid data left in the filteredObject.

Example 1:

Input:

obj = [-5, -4, -3, -2, -1, 0, 1],

fn = (x) => x > 0

Output: [1]

Explanation: All values that were not greater than 0 were removed.

Example 2:

Input:

obj = {"a": 1, "b": "2", "c": 3, "d": "4", "e": 5, "f": 6, "g": {"a": 1}},

fn = (x) => typeof x === "string"

Output:

Explanation: All keys with values that were not a string were removed. When the object keys were removed during the filtering process, any resulting empty objects were also removed.

Example 3:

Input:

obj = [-1, [-1, -1, 5, -1, 10], -1, [-1], [-5]],

fn = (x) => x > 0

Output: [[5,10]]

Explanation: All values that were not greater than 0 were removed. When the values were removed during the filtering process, any resulting empty arrays were also removed.

Example 4:

Input:

obj = [[[[5]]]],

fn = (x) => Array.isArray(x)

Output: undefined

Constraints:

• fn is a function that returns a boolean value
• obj is a valid JSON object or array
• 2 <= JSON.stringify(obj).length <= 10^5

题目大意

给定一个对象 obj 和一个函数 fn，返回一个经过筛选的对象 filteredObject。

函数 deepFilter 应该在对象 obj 上执行深度筛选操作。深度筛选操作应该移除筛选函数 fn 输出为 false 的属性，以及在键被移除后仍然存在的任何空对象或数组。

如果深度筛选操作导致对象或数组为空，没有剩余属性，deepFilter 应该返回 undefined，表示在 filteredObject 中没有有效数据。

示例 1：

输入：

obj = [-5, -4, -3, -2, -1, 0, 1],

fn = (x) => x > 0

输出：[1]

解释： 所有不大于 0 的值都被移除。

示例 2：

输入：

obj = {"a": 1, "b": "2", "c": 3, "d": "4", "e": 5, "f": 6, "g": {"a": 1}},

fn = (x) => typeof x === "string"

输出：

解释： 所有值不是字符串的键都被移除。在筛选过程中移除键后，任何导致为空的对象也被移除。

示例 3：

输入：

obj = [-1, [-1, -1, 5, -1, 10], -1, [-1], [-5]],

fn = (x) => x > 0

输出：[[5,10]]

解释： 所有不大于 0 的值都被移除。在筛选过程中移除值后，任何导致为空的数组也被移除。

示例 4：

输入：

obj = [[[[5]]]],

fn = (x) => Array.isArray(x)

输出： undefined

提示：

• fn 是一个返回布尔值的函数
• obj 是一个有效的 JSON 对象
• 2 <= JSON.stringify(obj).length <= 10**5

解题思路

1. 定义递归函数 dfs，用于对传入的对象或数组进行深度筛选，会对 obj 中的每个属性进行递归检查，符合条件的保留，不符合的剔除。

2. 递归处理数组：

   • 在 dfs 函数内，首先检查 obj 是否是数组。
   • 如果是数组，则对每个元素调用 dfs 递归处理并存储到新数组 res 中。
   • 之后，通过 filter 去除 undefined 项，仅保留有效数据。
   • 如果 res 数组有内容，返回 res，否则返回 undefined。

3. 递归处理对象：

   • 如果 obj 是对象，则创建一个空对象 res，然后遍历 obj 的每个属性。
   • 对每个属性调用 dfs 递归处理，并将结果存储在 filteredValue 中。
   • 如果 filteredValue 不为 undefined，将该属性和值保留在 res 中。
   • 遍历完成后，如果 res 不为空，返回 res；否则返回 undefined。

4. 处理基本数据类型：

   • 对于非对象和非数组的值，直接调用筛选函数 fn。
   • 如果 fn 返回 true，保留该值；
   • 否则返回 undefined 表示不保留。

5. 整个 dfs 处理完成后，返回筛选后的结果。

复杂度分析

• 时间复杂度：O(n)，其中 n 是对象的节点数，需要递归遍历每个节点。
• 空间复杂度：O(d)，其中 d 是对象的最大嵌套深度，主要是递归调用栈的开销。

代码

/**
 * @param {Object} obj
 * @param {Function} fn
 * @return {Object}
 */
var deepFilter = function (obj, fn) {
	const dfs = (obj) => {
		// 递归处理数组
		if (Array.isArray(obj)) {
			let res = obj.map(dfs).filter((i) => i !== undefined);
			return res.length > 0 ? res : undefined;
		}

		// 递归处理对象
		if (typeof obj == 'object' && obj != null) {
			let res = {};
			for (let key of Object.keys(obj)) {
				const filteredValue = dfs(obj[key]);
				if (filteredValue !== undefined) {
					res[key] = filteredValue;
				}
			}
			return Object.keys(res).length > 0 ? res : undefined;
		}

		// 处理基本数据类型
		return fn(obj) ? obj : undefined;
	};
	return dfs(obj);
};