时间戳

首页 > 解决方案 > 重构函数，使其为 O(N)

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

问题描述

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

我从过滤掉匹配项的 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();
        }

标签： c#.net

解决方案

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

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

推荐阅读