計算數組中出現的次數
1. 概述
一個常見的程式設計問題是計算清單中不同元素的出現次數或頻率。例如，當我們想知道一個或多個元素的最高或最低出現次數或特定出現次數時，它會很有幫助。
在本教程中，我們將了解一些計算數組中出現次數的常見解決方案。
2. 統計出現次數
我們需要了解這個問題的限制才能找到解決方案。
2.1.約束條件
首先，我們必須了解我們是否算數：
- 物體的出現次數
- 原語的出現
如果我們處理數字，我們需要知道要計算的值的範圍。這可能是一個小的固定值範圍，也可能是整個數字範圍，其中值顯示稀疏。
2.2.如何找到解決方案
對於int或char等原語，我們可以使用固定大小的計數器陣列來儲存每個值的頻率。這是可行的，但由於記憶體中可容納的計數數組的最大大小而存在限制。此外，將其擴展到物件是行不通的。
使用地圖是解決該問題的更具適應性的解決方案。
3. 使用計數器數組
讓我們對固定範圍內的正整數使用計數器數組。
3.1.計算固定範圍內的正整數
因此，假設我們有值 0…(n-1) 並且想知道它們的出現次數：
static int[] countOccurrencesWithCounter(int[] elements, int n) {
int[] counter = new int[n];
for (int i = 0; i < elements.length - 1; i++) {
counter[elements[i]]++;
}
return counter;
}演算法很簡單，在陣列上循環，同時遞增特定元素的計數器位置。
我們看一下演算法複雜度：
- 時間複雜度：存取陣列的
O(n) - 空間複雜度：
O(n)取決於輸入陣列的大小
讓我們來看一個單元測試，我們發現前十個數字中出現了數字3 ：
int[] counter = countOccurrencesWithCounter(new int[] { 2, 3, 1, 1, 3, 4, 5, 6, 7, 8 }, 10);
assertEquals(2, counter[3]);
計數器的另一個有趣的應用是字串中的字元。例如，我們可以查看字串排列中的頻率計數。
3.2.其他用例和限制
儘管數組的最大大小相當大，但將其用於頻率通常不是一個好習慣，除非我們知道我們正在計算的是一個有限集合。
將其用於稀疏範圍的值並不容易。例如，這適用於小數，其中找到合適的範圍來儲存小數將很困難。
對於負數，我們可以使用偏移量並將負數儲存在計數器中。例如，如果我們有一個代表 [ -k , k ] 值範圍的k偏移量，我們可以建立一個計數器陣列：
int[] counter = new int[(k * 2) + 1];
然後，我們可以儲存value + k位置處的出現。
這種方法有局限性，因為值的範圍可能不適合我們想要儲存頻率的實際值。而且，我們不能使用這個資料結構來統計物件出現的次數。
4. 使用地圖
地圖更適合計算出現次數。此外，映射的大小僅受可用 JVM 記憶體的限制，因此適合儲存大量條目。
就像計數器一樣，我們增加頻率，但這次，它與特定的映射鍵相關。 地圖使我們能夠處理對象。因此，我們可以使用泛型來建立具有泛型鍵的映射：
static <T> Map<T, Integer> countOccurrencesWithMap(T[] elements) {
Map<T, Integer> counter = new HashMap<>();
for (T element : elements) {
counter.merge(element, 1, Integer::sum);
}
return counter;
}我們看一下演算法複雜度：
- 時間複雜度：存取陣列的
O(n) - 空間複雜度：
O(m)，其中 m 是原始數組中不同值的數量
讓我們來看看找出整數出現次數的測驗。使用映射，我們還可以搜尋負整數：
Map<Integer, Integer> counter = countOccurrencesWithMap(new Integer[] { 2, 3, 1, -1, 3, 4, 5, 6, 7, 8, -1 });
assertEquals(2, counter.get(-1));
同樣，我們可以計算字串的出現次數：
Map<String, Integer> counter = countOccurrencesWithMap(new String[] { "apple", "orange", "banana", "apple" });
assertEquals(2, counter.get("apple"));
我們也可以使用 Guava Multiset 來儲存與特定鍵相關的頻率。
5. 使用 Java 8 流
從 Java 8 開始，我們可以使用流來收集按不同元素分組的出現次數。它的工作原理就像前面的地圖範例一樣。然而，使用流允許我們使用函數式編程並在可能的情況下利用並行執行。
讓我們來看看計算整數出現次數的情況：
static <T> Map<T, Long> countOccurrencesWithStream(T[] elements) {
return Arrays.stream(elements)
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}
值得注意的是，當我們使用陣列時，我們必須先轉換為流。
演算法的複雜度與使用地圖類似：
- 時間複雜度：存取陣列的
O(n) - 空間複雜度：
O(m)，其中 m 是數組的不同值的數量
使用流的優點可能與執行速度有關。但是，我們仍然需要迭代所有輸入元素並使用空間來建立出現的映射。
讓我們來看看整數的測試：
Map<Integer, Long> counter = countOccurrencesWithStream(new int[] { 2, 3, 1, -1, 3, 4, 5, 6, 7, 8, -1 });
assertEquals(2, counter.get(-1));
同樣，我們看一下字串的測試：
Map<String, Long> counter = countOccurrencesWithStream(new String[] { "apple", "orange", "banana", "apple" });
assertEquals(2, counter.get("apple"));
六，結論
在本文中，我們看到了計算數組中出現次數的解。最適應性強的解決方案是使用簡單的地圖或透過串流創建的地圖。然而，如果我們有固定範圍內的原始整數，我們可以使用計數器。
與往常一樣，本文中提供的程式碼可以在 GitHub 上取得。