查找字符串中出現次數最多的字符
一、概述
查找字符串中出現次數最多的字符是編程中的一項常見任務。
在本教程中，我們將討論在 Java 中實現該目標的各種方法。
2. 使用 Java Stream API
Stream API 是 Java 8 帶給我們的一個重要的新特性。首先，讓我們使用 Java Streams 解決問題。
但在我們深入實施之前，讓我們通過一個示例快速了解問題。假設我們有一個字符串INPUT1 ：
static final String INPUT1 = "aaaaaaaaaa(10) bbbbbbb ccccc dddd eee ff";在這裡， INPUT1中出現頻率最高的字符是“ a ”字符.所以，目標是找到' a '。
接下來，讓我們創建一個方法來解決問題：
static Character byStream(String input) {
return input.chars()
.mapToObj(x -> (char) x)
.collect(groupingBy(x -> x, counting()))
.entrySet()
.stream()
.max(comparingByValue())
.get()
.getKey();
}如我們所見，使用 Stream API，我們可以將多個方法調用鏈接到一個語句中。這是因為Java Stream API 採用了流暢的接口模式。
那麼接下來，讓我們了解這條語句是如何完成這項工作的：
-
input.chars()– 將輸入字符串分解為IntStream -
mapToObject( x -> (char) x)– 將整數轉換為char並將其“裝箱”為Character -
collect(groupingBy(x -> x, counting()))– 按Characters 分組, counting()出現，並將它們收集為Map<Character, Long> -
entrySet().stream()– 創建所有地圖條目的流 -
max(comparingByValue())– 通過條目的值找到最大的條目。在這裡，我們應該注意返回類型是Optional<Entry<Character, Long>> -
get()– 獲取入口對象 -
getKey()– 獲取條目的鍵，即出現次數最多的Character對象
現在我們了解了byStream()方法是如何工作的，讓我們測試它是否正確地完成了工作：
char result1 = CharacterWithHighestFrequency.byStream(INPUT1);
assertEquals('a', result1);當我們運行它時，測試通過了。所以，我們已經解決了這個問題。
該方法可以正常工作，直到有一天我們遇到如下輸入：
static final String INPUT2 = "YYYYYYY(7) bbbbb -------(7) dddd eee kkkkkkk(7) ff";在INPUT2中，三個字符以相同的頻率出現在字符串中 (7)：“ Y ”、“ – ”和“ k ”。如果要求將“ Y ”、“ – ”和“ k ”中的任何字符定義為正確結果，我們的byStream()方法仍然有效。
但是，如果我們需要所有最常見的字符，我們的解決方案將不再有效。
接下來，讓我們構建涵蓋INPUT1和INPUT2案例的解決方案。
3. 使用HashMap
HashMap維護鍵值關聯。我們可以創建一個HashMap<Character, Integer>來保存Character及其出現的映射。
然後，我們可以找到出現次數最多的條目。輸入鍵就是答案。
那麼接下來，讓我們將這個想法實現為一個方法：
static Set<Character> byMap(String input) {
Map<Character, Integer> map = new HashMap<>();
for (char c : input.toCharArray()) {
map.compute(c, (character, count) -> count == null ? 1 : ++count);
}
int maxCount = map.values()
.stream()
.mapToInt(Integer::intValue)
.max()
.getAsInt();
return map.keySet()
.stream()
.filter(c -> map.get(c) == maxCount)
.collect(toSet());
}上面的byMap()方法返回Set<Character>而不是單個char或Character對象。
接下來，讓我們快速瀏覽一下實現。
正如我們所討論的，我們首先創建一個空的Map對象。然後，我們遍歷輸入字符串中的字符並增加字符在映射中的出現次數。
值得一提的是，我們使用Map.compute()方法來簡化“如果一個鍵(Character)存在，增加它的值，否則創建一個條目： theCharacter: 1 ”的實現。
遍歷字符後，我們需要找到出現次數最多的字符。因此，我們使用 Stream API 找出maxCount 。我們還可以在循環字符時找到maxCount 。我們將在稍後的桶方法中看到這是如何完成的。
最後，我們再次使用 Stream API 收集出現次數為maxCount字符。
byMap()方法的一個目標是涵蓋INPUT1和INPUT2場景。我們可以編寫一個測試來驗證它是否按預期工作：
static final Set<Character> EXPECTED1 = Collections.singleton('a');
static final Set<Character> EXPECTED2 = ImmutableSet.of('Y', '-', 'k');
Set<Character> result1 = CharacterWithHighestFrequency.byMap(INPUT1);
assertEquals(EXPECTED1, result1);
Set<Character> result2 = CharacterWithHighestFrequency.byMap(INPUT2);
assertEquals(EXPECTED2, result2);4. 使用“桶”
我們了解到基於HashMap的方法保存character -> occurrences映射，然後找到出現次數最多的字符。假設我們只關注 ASCII 字符集，我們可以通過維護character -> occurrences associations with array來改進基於HashMap的解決方案。因此，我們可以節省Map和HashMap的開銷。
我們知道ASCII字符集由128個字符組成。此外，所有這 128 個字符的 ASCII 碼範圍從 0 到 127。因此，我們可以用 128 個元素（桶）初始化一個int[]數組。數組索引從 0 到 127，涵蓋了所有 ASCII 字符的 ASCII 碼。
我們在遍歷給定字符串的字符時增加相應的字符桶。
接下來我們在byBucket()方法中實現這個思路：
static Set<Character> byBucket(String input) {
int[] buckets = new int[128];
int maxCount = 0;
for (char c : input.toCharArray()) {
buckets[c]++;
maxCount = Math.max(buckets[c], maxCount);
}
int finalMaxCount = maxCount;
return IntStream.range(0, 128)
.filter(c -> buckets[c] == finalMaxCount)
.mapToObj(i -> (char) i)
.collect(Collectors.toSet());
}如上面的代碼所示， buckets是一個包含 128 個元素的數組。因為它是一個int[]原始數組，所以初始值都是零。
當我們遍歷字符時，我們簡單地通過buckets[c]++增加桶值。之後，我們也在循環中更新maxCount變量。因此，在循環之後，我們在maxCount變量中獲得了所有字符的出現次數和最高出現次數。
最後一步是找出哪個桶與maxCount具有相同的值，並將其索引轉換為Character對像作為答案。我們再次使用 Stream API 來做到這一點。
值得一提的是，我們將maxCount重新分配給另一個int變量，使其有效地最終化，以便filter()方法調用中的 lambda 表達式可以接受它。
最後，讓我們創建一個測試來覆蓋INPUT1和INPUT2案例，以檢查byBucket()方法是否按預期工作：
Set<Character> result1 = CharacterWithHighestFrequency.byBucket(INPUT1);
assertEquals(EXPECTED1, result1);
Set<Character> result2 = CharacterWithHighestFrequency.byBucket(INPUT2);
assertEquals(EXPECTED2, result2);如果我們試一試，測試就會通過。
5.結論
在本文中，我們探討瞭如何找到字符串中出現頻率最高的字符。我們通過示例討論了三種方法：
- 使用 Java Stream API 的單一語句解決方案
- 基於
HashMap的解決方案 - 基於桶的解決方案
與往常一樣，此處提供的所有代碼片段都可以在 GitHub 上找到。