從列表中找到最常見的對象

比方說，我有一個ListEmployee對象。 Employee對象有一個getDepartment方法，該方法返回一個Department對象。我想遍歷該列表以找到最多Employee的部門（即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; 
    } 
}

如果有兩個員工人數相同的部門，則返回哪個並不重要。

謝謝！

來源

2011-02-22 Adam

創建部門id - >計數的地圖。

這樣你就可以通過id獲得所有計數的集合。您還可以維護一個最大項目，該項目是對具有最高計數的地圖項目的引用。

算法將是這樣的：

1）初始化地圖和currentMax
2）通過員工
3）每個員工環路，獲知其部門ID
4）像做地圖獲得（currentId）
a）如果當前計數爲空時，將其初始化
5）增加計數
6）如果增加後的計數爲> currentMax，更新currentMax

該算法將運行在O（n）;我認爲你不可能比這更好。它的空間複雜度也是O（n），因爲計數的數量正比於輸入的大小。

如果您願意，您可以創建一個使用合成的類（即包含一個Map和一個List），並且還管理指向具有最高計數的Entry的指針。這樣，你的功能的這部分就被正確地封裝了。這種方法更強大的優勢在於，您可以在向列表中輸入項目時維護計數（您可以代理將員工添加到列表中的方法，以便更新地圖計數器）。雖然可能會過度。

來源

2011-02-22 22:35:07 hvgotcodes

我想過，我是想知道Java中是否有一個地圖數據結構可以跟蹤最高的Entry值。你知道嗎？ – Adam 2011-02-22 22:36:58

@adam，我不知道任何，儘管你可以保持一個單獨的引用與最高的計數Map.Entry。或者你可以寫你自己的類來封裝這個功能。 – hvgotcodes 2011-02-22 22:40:05

不是我所知道的，但是如果你真的想這麼做，那麼你可以擴展HashMap類......這可能會超出你程序的範圍。 – donnyton 2011-02-22 22:41:30

由於您只是要計算員工，因此製作地圖相對比較容易。

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-22 22:40:01 donnyton

嗯...我認爲這不會有幫助。問題在於找到擁有最多員工的部門。從部門ID到部門的映射不是問題的一部分，因爲每個員工都已經參考了部門。 – 2011-02-22 23:02:41

啊，我弄錯了這個問題。將編輯。 – donnyton 2011-02-22 23:03:51

這是一項改進，但您不需要保留員工名單。這個問題只需要計數。 – 2011-02-22 23:14:51

我會用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; 
    } 
}

您需要在Department這個工作正確執行equals和hashCode。

還有一個問題here提到在將來創建一個「排行榜」類型Multiset的可能性，它將根據它包含的每個條目的計數維持一個訂單。

來源

2011-02-22 22:52:52 ColinD

自從Guava 11開始實施：http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Multisets.html#copyHighestCountFirst%28com.google.common.collect.Multiset ％29 – lbalazscs 2012-12-20 20:43:32

我會那樣做，模== 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()，將做第一種方法的工作，但是這是更靈活，更guavish。只要記住C類應該被很好地實現，那就是equals（），hashCode（）並且實現Comparable。

這是你如何使用它：

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

作爲獎勵，你也可以用類似的方法得到的那麼頻繁元素，只是，飼料與Ordering.natural第一（）方法和做不要扭轉它。

來源

2013-10-24 12:53:29

這裏的香草的Java 8解決方案：

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

它通過員工的名單最多兩次。使用jOOλ，如果你願意加入一個第三方的依賴等效的解決方案，是這樣的：

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

（聲明：我身後jOOλ公司工作）

來源

2016-03-20 10:21:11

從列表中找到最常見的對象

回答

相關問題