Skip to content

Latest commit

 

History

History
122 lines (87 loc) · 3.97 KB

File metadata and controls

122 lines (87 loc) · 3.97 KB
comments difficulty edit_url
true
中等

English Version

题目描述

给定一个对象 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"
输出:{"b":"2","d":"4"}
解释:所有值不是字符串的键都被移除。在筛选过程中移除键后,任何导致为空的对象也被移除。

示例 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

解法

方法一:递归

我们先判断当前对象是否为数组,如果是数组,我们就对数组中的每一个元素进行递归调用,然后过滤掉返回值为 undefined 的元素,最后返回过滤后的数组。

如果当前对象不是数组,我们就判断当前对象是否为对象,如果是对象,我们就对对象中的每一个属性值进行递归调用,然后过滤掉返回值为 undefined 的属性值,最后返回过滤后的对象。

如果当前对象既不是数组也不是对象,我们就直接返回 fn(obj) ? obj : undefined

时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为对象中的元素个数。

TypeScript

function deepFilter(obj: Record<string, any>, fn: Function): Record<string, any> | undefined {
    const dfs = (data: any): any => {
        if (Array.isArray(data)) {
            const res = data.map(dfs).filter((item: any) => item !== undefined);
            return res.length > 0 ? res : undefined;
        }
        if (typeof data === 'object' && data !== null) {
            const res: Record<string, any> = {};
            for (const key in data) {
                if (data.hasOwnProperty(key)) {
                    const filteredValue = dfs(data[key]);
                    if (filteredValue !== undefined) {
                        res[key] = filteredValue;
                    }
                }
            }
            return Object.keys(res).length > 0 ? res : undefined;
        }
        return fn(data) ? data : undefined;
    };

    return dfs(obj);
}