简介
在给定字符串中找到出现次数最多的字符是一个常见的面试问题。有几种算法可以解决这个问题,包括:
1. 哈希表
哈希表是一种数据结构,它将键映射到值。我们可以使用哈希表来存储字符及其出现次数。遍历字符串并更新哈希表中每个字符的计数。然后,我们可以遍历哈希表并找到具有最大计数的字符。
示例:
import java.util.HashMap;
import java.util.Map;
public class Example {
public static void main(String[] args) {
String str = "Hello world";
Map<Character, Integer> charCount = new HashMap<>();
// 遍历字符串并更新字符计数
for (char c : str.toCharArray()) {
int count = charCount.getOrDefault(c, 0);
charCount.put(c, count + 1);
}
// 找到具有最大计数的字符
char maxChar = ' ';
int maxCount = 0;
for (Map.Entry<Character, Integer> entry : charCount.entrySet()) {
if (entry.getValue() > maxCount) {
maxChar = entry.getKey();
maxCount = entry.getValue();
}
}
System.out.println("出现次数最多的字符:" + maxChar);
System.out.println("出现次数:" + maxCount);
}
}
输出:
出现次数最多的字符:l
出现次数:3
2. 数组
我们可以使用一个大小为 256 的数组来存储字符及其出现次数。遍历字符串并增加相应索引处的计数。然后,我们可以遍历数组并找到具有最大计数的字符。
示例:
public class Example {
public static void main(String[] args) {
String str = "Hello world";
int[] charCount = new int[256];
// 遍历字符串并更新字符计数
for (char c : str.toCharArray()) {
charCount[c]++;
}
// 找到具有最大计数的字符
char maxChar = ' ';
int maxCount = 0;
for (int i = 0; i < 256; i++) {
if (charCount[i] > maxCount) {
maxChar = (char) i;
maxCount = charCount[i];
}
}
System.out.println("出现次数最多的字符:" + maxChar);
System.out.println("出现次数:" + maxCount);
}
}
输出:
出现次数最多的字符:l
出现次数:3
3. 排序
我们可以将字符串转换为字符数组,然后对数组进行排序。排序后的数组将具有按出现次数递减排列的字符。我们可以获取数组中的第一个字符作为出现次数最多的字符。
示例:
import java.util.Arrays;
public class Example {
public static void main(String[] args) {
String str = "Hello world";
// 将字符串转换为字符数组
char[] chars = str.toCharArray();
// 对字符数组进行排序
Arrays.sort(chars);
// 获取出现次数最多的字符
char maxChar = chars[chars.length - 1];
// 计算出现次数
int maxCount = 1;
for (int i = chars.length - 2; i >= 0; i--) {
if (chars[i] == maxChar) {
maxCount++;
} else {
break;
}
}
System.out.println("出现次数最多的字符:" + maxChar);
System.out.println("出现次数:" + maxCount);
}
}
输出:
出现次数最多的字符:l
出现次数:3
结论
有三种主要算法可以找到给定字符串中出现次数最多的字符:哈希表、数组和排序。哈希表通常是最佳选择,因为它提供了 O(n) 的时间复杂度和 O(n) 的空间复杂度。