在 Java 中尋找數組中整數的眾數
1. 概述
在本文中，我們將探討如何使用 Java 找出陣列中整數的眾數。
在 Java 中處理資料集時，我們可能經常需要尋找統計量測，例如平均值、中位數和眾數。眾數是資料集中出現最頻繁的數值。**如果沒有重複的數字，則資料集沒有眾數。如果多個數字具有相同的最高頻率，則所有這些數字都被視為眾數。**
2. 理解問題
這個演算法的目的是找到數組中整數的眾數。讓我們考慮一些例子：
nums = {1, 2, 2, 3, 3, 4, 4, 4, 5} 。該數組的模式為4 。
nums = {1, 2, 2, 1} 。此數組的眾數為{1, 2} 。
對於我們的程式碼，我們有一個整數數組範例：
int[] nums = { 1, 2, 2, 3, 3, 4, 4, 4, 5 };3. 使用排序
尋找眾數的一種方法是對陣列進行排序並找到最頻繁的元素。這種方法利用了這樣一個事實：在排序數組中，重複元素是相鄰的。我們來看一下程式碼：
Arrays.sort(nums);
int maxCount = 1;
int currentCount = 1;
Set<Integer> modes = new HashSet<>();
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
currentCount++;
}
else {
currentCount = 1;
}
if (currentCount > maxCount) {
maxCount = currentCount;
modes.clear();
modes.add(nums[i]);
}
else if (currentCount == maxCount) {
modes.add(nums[i]);
}
}
if (nums.length == 1) {
modes.add(nums[0]);
}此方法對輸入數組進行排序，然後遍歷它來統計每個數字的出現頻率。它會追蹤頻率最高的數字並相應地更新模式列表。它還處理數組僅包含一個元素的邊緣情況。
讓我們來看看時間複雜度和空間複雜度：
- 時間複雜度：由於排序步驟，
O(n log n)。 - 空間複雜度：如果使用的排序演算法是歸併排序，則在最壞情況下為
O(n)如果我們只考慮用於儲存眾數的額外空間，則為O(k)。
這裡， n是數組中元素的數量， k是模式的數量。
4. 使用頻率數組
如果數組中整數的範圍已知且有限，則頻率數組可能是一個非常有效的解決方案。此方法使用陣列索引來計算出現次數。讓我們看看如何：
Map<Integer, Integer> frequencyMap = new HashMap<>();
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
int maxFrequency = 0;
for (int frequency : frequencyMap.values()) {
if (frequency > maxFrequency) {
maxFrequency = frequency;
}
}
Set<Integer> modes = new HashSet<>();
for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
if (entry.getValue() == maxFrequency) {
modes.add(entry.getKey());
}
}此方法使用數組中每個整數的頻率填充映射，然後確定映射中存在的最高頻率。最後，它從映射中收集頻率最高的所有整數。
讓我們來看看時間複雜度和空間複雜度：
- 時間複雜度：
O(n + m)，在平均情況下簡化為O(n)因為m通常遠小於n。 - 空間複雜度：
O(m + k)。在最壞的情況下，如果所有元素都是唯一的且每個元素都是一個模式，則這可能是O(n)。
這裡， n是數組中元素的數量， m是數組中唯一元素的數量， k是模式的數量。
5. 使用TreeMap
TreeMap可以提供排序的頻率圖，這在某些情況下可能很有用。邏輯如下：
Map<Integer, Integer> frequencyMap = new TreeMap<>();
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
int maxFrequency = 0;
for (int frequency : frequencyMap.values()) {
if (frequency > maxFrequency) {
maxFrequency = frequency;
}
}
Set<Integer> modes = new HashSet<>();
for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
if (entry.getValue() == maxFrequency) {
modes.add(entry.getKey());
}
}使用的方法與上一節所使用的方法相同。唯一的區別是我們在這裡使用了TreeMap 。使用TreeMap可確保元素按排序順序存儲，這對於需要排序鍵的進一步操作非常有用。
讓我們來看看時間複雜度和空間複雜度：
- 時間複雜度：
O(n log m + m)，在平均情況下簡化為O(n log m)。 - 空間複雜度：
O(m + k).在最壞的情況下，如果所有元素都是唯一的且每個元素都是一個模式，則這可能是O(n)。
這裡， n是數組中元素的數量， m是數組中唯一元素的數量， k是模式的數量。
6. 使用流
當處理大型資料集時，我們可以利用Java的平行流來利用多核心處理器。邏輯如下：
Map<Integer, Long> frequencyMap = Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(e -> e, Collectors.counting()));
long maxFrequency = Collections.max(frequencyMap.values());
Set<Integer> modes = frequencyMap.entrySet()
.stream()
.filter(entry -> entry.getValue() == maxFrequency)
.map(Map.Entry::getKey)
.collect(Collectors.toSet());程式碼使用 Java 流以函數式方式處理數組。這使得程式碼簡潔且富有表現力。
首先，我們將原始整數轉換為Integer對象，以便它可以與通用流操作一起使用，然後我們按值對整數進行分組，並使用Collectors.groupingBy()和Collectors.counting().使用Collections.max()可以找到最大頻率。最後，過濾頻率最高的條目，並將它們的鍵收集到一個清單中。
此方法非常高效，並利用 Java Stream API 的強大功能以乾淨且可讀的方式尋找模式。
讓我們來看看時間複雜度和空間複雜度：
- 時間複雜度：
O(n + m)，在平均情況下簡化為O(n)因為m通常遠小於n。 - 空間複雜度：
O(m + k)。在最壞的情況下，如果所有元素都是唯一的且每個元素都是一個模式，則這可能是O(n)。
這裡， n是數組中元素的數量， m是數組中唯一元素的數量， k是模式的數量。
七、結論
在本教程中，我們探索了尋找數組中整數眾數的各種方法。這些方法各有優點，適合不同的場景。以下是幫助我們選擇正確方法的快速總結：
- 排序：對於中小型陣列簡單有效
- 頻率數組：如果數字範圍很小，效率很高
-
TreeMap：如果我們需要排序的頻率圖，則很有用 - 並行流：非常適合大型資料集利用多個核心
透過根據我們的具體需求選擇合適的方法，我們可以優化Java中尋找數組中整數眾數的過程。
所有這些範例的源代碼都可以在 GitHub 上取得。