c# - 重构函数，使其为 O(N)

Question

我为下拉树获取了一堆类别，并且必须在这个下拉列表中实现搜索。如果其中一个元素匹配，它还应该让所有父元素显示在下拉层次结构中。

我从 2 个 foreach 循环开始，在其中过滤掉匹配项，在一个循环中检查 parentId 的匹配项并递归添加父项直到没有剩余( parentId == 0).

public ScrapCategory[] Filter(ScrapCategory[] categories, string searchString)
{
    var result = new List<ScrapCategory>();

    foreach (ScrapCategory category in categories)
    {
        if (category.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0)
            result.Add(category);

        if (category.ParentId == 0)
            continue;

        ScrapCategory currentParent = categories.Where(x => x.Id == category.ParentId).First();

        if (!result.Contains(currentParent))
            result.Add(currentParent);

        while (currentParent?.ParentId > 0)
        {
            currentParent = categories.Where(x => x.Id == currentParent.ParentId)?.First();
            if (!result.Contains(currentParent))
                result.Add(currentParent);
        }
    }

    return result.OrderBy(x => x.Level).ToArray();
}

我得到了预期的结果，但我希望在 O(N) 中看到这个结果，因此只有 categories 没有那些 .Where() 子句的交互。

编辑:我设法去掉了一个 .Where() 子句。

 public ScrapCategory[] Filter(ScrapCategory[] categories, string searchString)
        {
            var result = new List<ScrapCategory>();

            foreach (ScrapCategory category in categories)
            {
                if (category.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0)
                    result.Add(category);

                if (category.ParentId > 0)
                {
                    int parentId = category.ParentId;

                    while (parentId > 0)
                    {
                        var parent = categories.Where(x => x.Id == parentId)?.First();
                        if (!result.Contains(parent))
                            result.Add(parent);
                        parentId = parent.ParentId;
                    }
                }
            }

            return result.OrderBy(x => x.Level).ToArray();
        }

Answer 1

这是我的最终结果，我很满意。

public ScrapCategory[] Filter(ScrapCategory[] categories, string searchString)
    {
        var lookup = categories.ToDictionary(category => category.Id);
        var result = new HashSet<ScrapCategory>();
        foreach (ScrapCategory category in categories)
        {
            if (category.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0)
                result.Add(category);
            int parentId = category.ParentId;
            while (parentId > 0)
            {
                ScrapCategory parent = lookup[parentId];
                if (!result.Add(parent))
                    break;
                parentId = parent.ParentId;
            }
        }
        return result.OrderBy(n => n.Level).ToArray();
    }