2

List私がEmployeeオブジェクトを持っているとしましょう。Employeeオブジェクトには、オブジェクトgetDepartmentを返すメソッドがありますDepartment。Employeeそのリストを繰り返し処理して、 sが最も多い部門（つまり、Departmentオブジェクトが最も頻繁に返される）を見つけたいと思いますgetDepartment。これを行うための最速の方法は何ですか？

public class Employee{

   static allEmployees = new ArrayList<Employee>();       

   int id;
   Department department;

   public Employee(int id, Department department){
     this.id = id;
     this.department = department;
     allEmployees.add(this);
   }

   public Department getDepartment(){
     return department;
   }

   public static List<Employee> getAllEmployees(){
      return allEmployees;
   }
}

public class Department{
   int id;
   String name;

   public Department(int id){
     this.id = id;
   }

   public String getName(){
     return name;
   }
}

同数の従業員がいる2つの部門がある場合、どちらが返されるかは問題ではありません。

ありがとう！

4

5 に答える 5

3

部門 ID -> カウントのマップを作成します。

そうすれば、ID ごとにすべてのカウントのコレクションを取得できます。最大カウントのマップ エントリへの参照である最大アイテムを維持することもできます。

アルゴリズムは次のようになります。

1) Map と currentMax を初期化する
2) 従業員をループする
3) 各従業員の部門 ID を取得する
4) map.get(currentId) などを実行
する a) 現在のカウントが null の場合は初期化する
5) カウントをインクリメントする
6) 増分されたカウントが > currentMax の場合、currentMax を更新します。

このアルゴリズムは O(n) で実行されます。私はあなたがそれよりも良くなるとは思わない。カウント数は入力のサイズに比例するため、そのスペースの複雑さも O(n) です。

必要に応じて、コンポジションを使用する (つまり、Map と List を含む) クラスを作成し、最大カウントの Entry へのポインターを保持することもできます。そうすれば、機能のこの部分が適切にカプセル化されます。このアプローチのより強力な利点は、アイテムをリストに入力するときにカウントを維持できることです (従業員をリストに追加するメソッドをプロキシして、マップ カウンターを更新します)。やり過ぎかもしれませんが。

于 2011-02-22T22:35:07.153 に答える
2

以下はバニラの Java 8 ソリューションです。

Employee.getAllEmployees()
        .stream()
        .collect(Collectors.groupingBy(Employee::getDepartment, Collectors.counting()))
        .entrySet()
        .stream()
        .max(Comparator.comparing(Entry::getValue))
        .ifPresent(System.out::println);

従業員のリストを最大 2 回通過します。サードパーティの依存関係を追加する場合、jOOλを使用した同等のソリューションは次のとおりです。

Seq.seq(Employee.getAllEmployees())
   .grouped(Employee::getDepartment, Agg.count())
   .maxBy(Tuple2::v2)
   .ifPresent(System.out::println);

（免責事項：私はjOOλの背後にある会社で働いています）

于 2016-03-20T10:21:11.757 に答える
1

Guavaを使用して次のようなことを行います。

Multiset<Department> departments = HashMultiset.create();
for (Employee employee : employees) {
  departments.add(employee.getDepartment());
}

Multiset.Entry<Department> max = null;
for (Multiset.Entry<Department> department : departments.entrySet()) {
  if (max == null || department.getCount() > max.getCount()) {
    max = department;
  }
}

equalsこれを機能させるには、 and hashCodeonを正しく実装する必要がありますDepartment。

ここMultisetには、含まれる各エントリの数に基づいて順序を維持する「リーダーボード」タイプを将来作成する可能性について言及している問題もあります。

于 2011-02-22T22:52:52.477 に答える
0

従業員を数えたいだけなので、マップを作成するのは比較的簡単です。

HashMap<Department, Integer> departmentCounter;

部門を従業員数にマップします (従業員ごとにカウントを増やします)。または、リストを使用して従業員全体をマップに保存できます。

HashMap<Department, List<Employee>> departmentCounter;

代わりにリストのサイズを見てください。

クラスの使用方法がわからない場合は、HashMap のドキュメントを参照してください: http://download.oracle.com/javase/1.4.2/docs/api/java/util/HashMap.html

ヒント: HashMap.keySet() を使用して、どの部門が入力されたかを確認する必要があります。

于 2011-02-22T22:40:01.660 に答える
0

modulo == null および isEmpty チェックのようにします。

public static <C> Multimap<Integer, C> getFrequencyMultimap(final Collection<C> collection,
    final Ordering<Integer> ordering) {
    @SuppressWarnings("unchecked")
    Multimap<Integer, C> result = TreeMultimap.create(ordering, (Comparator<C>) Ordering.natural());
    for (C element : collection) {
        result.put(Collections.frequency(collection, element), element);
    }
    return result;
}

public static <C> Collection<C> getMostFrequentElements(final Collection<C> collection)       {
    Ordering<Integer> reverseIntegerOrdering = Ordering.natural().reverse();
    Multimap<Integer, C> frequencyMap = getFrequencyMultimap(collection, reverseIntegerOrdering);
    return frequencyMap.get(Iterables.getFirst(frequencyMap.keySet(), null));
}

最初のメソッドのジョブを実行するCollectionUtils.getCardinalityMap()もありますが、これはより柔軟で、よりガビッシュです。

C クラスは適切に実装されている必要があることに注意してください。つまり、equals()、hashCode() があり、Comparable が実装されています。

これはあなたがそれを使用する方法です：

Collection<Dummy> result = LambdaUtils.getMostFrequentElements(list);

おまけとして、同様のメソッドを使用して頻度の低い要素を取得することもできます。最初のメソッドに Ordering.natural() を入力し、元に戻さないでください。

于 2013-10-24T12:53:29.747 に答える