11

问题是这样的

建议一个数据结构并编写一个程序来计算员工在线性时间内（直接或间接）推荐的员工数量。例如

  A B C D E F G 
A 0 1 0 0 0 0 0 A referred 4 (A referred B, B referred C and D and D referred E)
B 0 0 1 1 0 0 0 B referred 3 
C 0 0 0 0 0 0 0
D 0 0 0 0 1 0 0 D referred 1
E 0 0 0 0 0 0 0
F 0 0 0 0 0 0 1 F referred 1
G 0 0 0 0 0 0 0

这是使用二维数组完成的，可以在线性时间内完成吗？

请注意，员工显然不能被他直接或间接推荐的人推荐，因此图中不会有循环。一名新员工只能由一名员工推荐。而每个员工可以推荐多个员工。

4

6 回答 6

2

我使用 C# 的解决方案，我很确定这小于 N^2，但我需要再看一会儿。在我这样做的同时发表评论。

public class Employee
{
    public List<Employee> Referred { get; set; }
    public string Name { get; set; }
    public int CountOfRefer { get; set; }
    public bool BeenCounted { get; set; }
    public Employee()
    {
        Referred = new List<Employee>();
    }
}

    public static void main()
    {
        Employee A = new Employee(){ Name="A" };
        Employee B = new Employee(){ Name="B" };
        Employee C = new Employee(){ Name="C" };
        Employee D = new Employee(){ Name="D" };
        Employee E = new Employee(){ Name="E" };
        Employee F = new Employee(){ Name="F" };
        Employee G = new Employee(){ Name="G" };

        A.Referred.Add(B);
        B.Referred.Add(C);
        B.Referred.Add(D);
        D.Referred.Add(E);
        F.Referred.Add(G);
        List<Employee> employees = new List<Employee>()
        {
            A, B, C, D, E, F, G
        };

        foreach (var emp in employees)
        {
            if (!emp.BeenCounted) countRefers(emp);
        }
    }

    private static int countRefers(Employee emp)
    {
        if (!emp.BeenCounted && emp.Referred.Count != 0)
        {
            foreach (var refs in emp.Referred)
            {
                emp.CountOfRefer += countRefers(refs);
            }
        }

        emp.BeenCounted = true;
        emp.CountOfRefer += emp.Referred.Count;
        return emp.CountOfRefer;
    }

基本上在计算员工时，它会沿着树递归，直到找到一个没有推荐人的人（应该保证在那里，因为人们不能互相推荐（我想除非只有一个人，暂时忽略这种情况））。然后，如果它必须通过递归计算任何人，它会设置一个标志，因此它不需要再次计算它。

于 2013-07-31T20:13:58.537 回答
0

Java如果允许作弊：枚举可能代表图形。先写 A(B), B(C, D), ... 然后重新排序，这样就没有编译器抱怨的前向引用。（这对于非循环引用总是可能的。即使是针对循环引用的编译时检查。）

public class Refers {
    enum RefEnum {
        C(),
        E(),
        G(),
        D(E),
        F(G),
        B(C, D),
        A(B);

        //private final RefEnum[] refs;
        public final int refCount;

        private RefEnum(final RefEnum... refs) {
            //this.refs = refs;
            int n = 0;
            for (RefEnum ref : refs) {
                 n += 1 + ref.refCount;
            }
            refCount = n;
        }
    }

    public static void main(String[] args) {
        for (RefEnum ref : RefEnum.values()) {
            System.out.printf("%s has %d refers%n",
                    ref.toString(), ref.refCount);
        }
    }
}

然而，该算法保持 O(N²)。

于 2013-07-31T21:20:53.867 回答
0

您可以维护所有员工的邻接列表（N 个空间）。然后对于每个员工，为所有被推荐的员工维护一个类似 Bag 的数据结构。然后要计算员工 A 的引用，您可以从 A 开始运行 DFS（深度优先搜索），这是线性时间算法。

Java代码在这里 -

http://yogeshsp.blogspot.com/2013/04/graph-api.html

http://yogeshsp.blogspot.com/2013/05/depth-first-search-dfs-graph-processing.html

于 2013-08-02T16:48:58.973 回答
0

图法：首先构造一个有向图（在这种情况下是一棵树），其中每个节点代表一个员工，并指向引用他们的员工的节点。这应该采用 O(N^2) 最坏情况（准确地说是 (N^2)/2 检查），其中 N 是员工人数。在构建此图表时，您应该跟踪此树的叶子（未推荐任何人的员工），然后修剪这些节点（将零分配给他们的推荐数量）并将推荐数量加 1推荐他们的员工。然后用新叶子重复，除了在它们的每个引用节点的引用数中添加 2。整个修剪和计数过程也应该花费 O(N)，最后所有节点都包含每个员工的推荐次数。

这是假设您的图表中没有循环或奇怪的两个员工引用同一员工的情况（即它实际上是一棵树）。

所以，不，如果问题的输入数据是您描述的二进制向量，则不能线性完成。如果我们只给出每个节点的雇佣员工的姓名，那么 O(N) 是可能的。

于 2013-07-31T20:12:09.040 回答
0

您可以先构建图表。这不能包含在 O(n) 中，因为它显然是 O(n^2)

不清楚是否优化重复引用（想象所有值都是 1）

此时，您可以从一个节点开始并添加所有引用的节点，例如在位掩码中。添加的任何值都需要递归导航，直到不添加新节点。

您访问的节点数是 O(N)，因为每个员工可以推荐一个人。

于 2013-07-31T20:14:19.547 回答
0

这是一棵树（更准确地说是一片森林）。在 O(n) 时间内读取边缘。在 O(n.log(n)) 中构建树。给定一个节点，访问并计算 O(n) 中的后代。

于 2013-07-31T21:31:59.263 回答