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

2次元配列を使用してこれを行いましたが、線形時間で実行できますか?

従業員は、直接的または間接的に推薦された人から明らかに推薦されないことに注意してください。そのため、グラフには循環がありません。新入社員を推薦できるのは、1 人の社員のみです。各従業員は複数の従業員を推薦できます。

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

基本的に、従業員をカウントするとき、参照していない人が見つかるまでツリーを再帰します (人々はお互いを参照できないため、そこにいることが保証されるべきです (今のところそのケースを無視して、1人しかいない場合を除きます) )))。次に、再帰を通じて誰かを計算する必要がある場合は、フラグを設定して、再度計算する必要がないようにします。

于 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

これは木（より正確には森）です。O(n) 時間でエッジを読み取ります。O(n.log(n)) でツリーを構築します。ノードを指定して、O(n) の子孫にアクセスしてカウントします。

于 2013-07-31T21:31:59.263 に答える
0

グラフの方法: まず、各ノードが従業員を表し、従業員を紹介した従業員のノードを指す有向グラフ (この場合はツリー) を作成します。これは、O(N^2) 最悪のケース (正確には (N^2)/2 チェック) を取る必要があります。ここで、N は従業員の数です。このグラフを作成するときは、このツリーの葉 (誰も紹介しなかった従業員) を追跡し、これらのノードをトリミングして (紹介の数に 0 を割り当て)、紹介の数に 1 を追加する必要があります。それらを紹介した従業員の。次に、参照ノードの数に 2 を追加することを除いて、新しいリーフで繰り返します。このトリミングとカウントのプロセス全体も O(N) かかる必要があり、最後にすべてのノードに各従業員が行った紹介の数が含まれます。

これは、グラフにサイクルや奇妙な 2 人の従業員が同じ従業員を参照する状況がないことを前提としています (つまり、実際にはツリーです)。

したがって、問題への入力データがあなたが説明したバイナリベクトルである場合、線形に行うことはできません。各ノードで雇用された従業員の名前だけが与えられた場合、O(N) が可能になります。

于 2013-07-31T20:12:09.040 に答える
0

最初にグラフを作成できます。これは明らかに O(n^2) であるため、O(n) に含めてはなりません。

重複した参照を最適化するかどうかは明確ではありません (すべての値が 1 であると想像してください)

この時点で、1 つのノードから始めて、すべての参照ノードをビット マスクなどで追加できます。追加された値は、新しいノードを追加しなくなるまで再帰的にナビゲートする必要があります。

各従業員は 1 人を紹介できるため、訪問するノードの数は O(N) です。

于 2013-07-31T20:14:19.547 に答える
0

すべての従業員の隣接リストを維持できます (N スペース)。次に、従業員ごとに、紹介されたすべての従業員のバッグのようなデータ構造を維持します。次に、従業員 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 に答える