1. 概述
在这个简短的教程中,我们将学习如何在Java数组中找到n个最常见的元素。
2. 使用HashMap
和PriorityQueue
我们可以使用HashMap
来统计每个元素出现的次数,并使用PriorityQueue
(优先队列)根据元素的计数对其进行排序。这样,我们就能高效地找出数组中n个最常见的元素:
public static List<Integer> findByHashMapAndPriorityQueue(Integer[] array, int n) {
Map<Integer, Integer> countMap = new HashMap<>();
// For each element i in the array, add it to the countMap and increment its count
for (Integer i : array) {
countMap.put(i, countMap.getOrDefault(i, 0) + 1);
}
// Create a max heap (priority queue) that will prioritize elements with higher counts.
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> countMap.get(b) - countMap.get(a));
// Add all the unique elements in the array to the heap.
heap.addAll(countMap.keySet());
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n && !heap.isEmpty(); i++) {
// Poll the highest-count element from the heap and add it to the result list.
result.add(heap.poll());
}
return result;
}
让我们测试一下我们的方法:
Integer[] inputArray = {1, 2, 3, 2, 2, 1, 4, 5, 6, 1, 2, 3};
Integer[] outputArray = {2, 1, 3};
assertThat(findByHashMapAndPriorityQueue(inputArray, 3)).containsExactly(outputArray);
3. 使用流API
我们也可以利用流API创建一个Map
来统计每个元素的出现次数,然后按频率降序对Map
中的条目进行排序,最后提取出n个最常见的元素:
public static List<Integer> findByStream(Integer[] arr, int n) {
return Arrays.stream(arr).collect(Collectors.groupingBy(i -> i, Collectors.counting()))
.entrySet().stream()
.sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
.map(Map.Entry::getKey)
.limit(n)
.collect(Collectors.toList());
}
4. 使用TreeMap
另一种选择是使用TreeMap
,并创建一个自定义的Comparator
,用于比较Map.Entry
对象中Map
值的频率,按照降序排序:
public static List<Integer> findByTreeMap(Integer[] arr, int n) {
// Create a TreeMap and use a reverse order comparator to sort the entries by frequency in descending order
Map<Integer, Integer> countMap = new TreeMap<>(Collections.reverseOrder());
for (int i : arr) {
countMap.put(i, countMap.getOrDefault(i, 0) + 1);
}
// Create a list of the map entries and sort them by value (i.e. by frequency) in descending order
List<Map.Entry<Integer, Integer>> sortedEntries = new ArrayList<>(countMap.entrySet());
sortedEntries.sort((e1, e2) -> e2.getValue().compareTo(e1.getValue()));
// Extract the n most frequent elements from the sorted list of entries
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n && i < sortedEntries.size(); i++) {
result.add(sortedEntries.get(i).getKey());
}
return result;
}
5. 总结
总的来说,我们了解了在Java数组中找到n个最常见的元素的不同方法。
本文示例代码可以在GitHub上找到。