查找字符串中，出现最先出现最多的字符
2019-02-18 本文已影响0人
Mr_UU
查找字符串中，出现最先出现最多的字符
查找字符串中最先出现次数最多的字符。首先需要查找出现次数最多的字符串，然后查找最多的字符串中出现最早的哪一个字符。
分析：遍历字符串即可统计到各个字符出现的次数；统计最早且最多的字符时，一般有两种思路：
- 记录各个字符出现的顺序。找到出现最多的次数后，结合字符出现的顺序即可获取到出现最早的字符；
- 逆序遍历字符串。顺序遍历一边不容易查找到最早出现的字符，但是能够找到最晚出现最多的字符。所以逆序遍历字符串，找到最晚出现的字符，那么就找到了最早出现最多次数的字符了。
结合着两种思路，一般有一下几种方法实现。
- 使用map，遍历两边。第一遍，遍历字符串数组， 统计各个字符出现的次数，并记录出现最多的次数N；第二遍，遍历字符串，从map中获取字符出现次数，找到第一个出现次数为N的字符。
public static char cal2(String str) {
Map<Character,Integer> map = new HashMap<>(MAX_CHAR_INT);
char[] ch = str.toCharArray();
for (int i = 0;i<ch.length;i++) {
if(map.containsKey(ch[i])){
map.put(ch[i],map.get(ch[i])+1);
}else {
map.put(ch[i],1);
}
}
int index = -1 ;
char maxChar = ch[0];
for(int i = 0 ;i<ch.length;i++){
if(map.get(ch[i]) > index ){
index = map.get(ch[i]);
maxChar = ch[i] ;
}
}
return maxChar;
}
- 使用map，逆序遍历一次。逆序遍历字符数组，记录出现次数最多的字符C和最多次数N，由于是逆序遍历，最后记录到的字符就是最早出现且出现次数最多的字符。
public static char cal3(String str) {
Map<Character,Integer> map = new HashMap<>(MAX_CHAR_INT);
char[] ch = str.toCharArray();
int max = 0 ;
char res = ch[0] ;
for (int i = ch.length -1 ; i >= 0;i --) {
if(map.containsKey(ch[i])){
map.put(ch[i],map.get(ch[i])+1);
if(map.get(ch[i]) >= max ){
max = map.get(ch[i]);
res = ch[i] ;
}
}else {
map.put(ch[i],1);
}
}
return res ;
}
- 使用数组。首先字符的个数是有限的（Character.MAX_VALUE-1个），可以使用数组，使数组的每个下标对应一个字符（char和int可以相互抓换），基于这一点可以使用数组nums来记录各个字符出现的次数，使用orders数组记录各个字符出现的顺序（字符出现次数为0时表示第一次出现，此时将该字符记录在orders数组最后）。
执行步骤：
- 记录各字符出现次数及出现顺序：通过一次遍历即可获取到所有字符出现的次数及顺序（效率O(n)）；
- 查找出现最多的字符：通过一次对nums表的遍历就能找到最多值max，同时记录对应的下标（效率为固定值(Character.MAX_VALUE-1)）；
- 查找出现最早且最多的字符：检验是否有多个出现次数最多的字符（如a/b都出现了100次），找到在orders表里出现最早的。从第二步中的下标开始遍历nums，找到出现次数为max的下标，遍历ordres找到其出现顺序（记录最小下标值）。当nums遍历完成后，记录到的orders最小下标即出现最早的字符。此过程效率最优为1，此时int值最大的字符出现次数最多的字符，且第一个出现；效率最差为log2(n)，此时所有字符出现次数均相同。
public static Character findFirstMaxChar(@NonNull String str){
int indx = 0;
char[] orders = new char[MAX_CHAR_INT];
int[] nums = new int[MAX_CHAR_INT];
for(int i = 0, len = str.length(); i < len; i ++){
char c = str.charAt(i);
if(nums[c] > 0){
nums[c] = nums[c] + 1;
} else {
nums[c] = 1;
orders[indx ++] = c;
}
}
//find max num
int max = 0, maxIndx = 0;
for (int i = 0; i < nums.length; i++) {
if( max < nums[i] ){
max = nums[i];
maxIndx = i;
}
}
// find first max num char
int minIndx = orders.length-1;
for(int i = maxIndx; i < nums.length; i ++){
if(nums[i] < max){
continue;
}
for (int j = 0; j < minIndx; j++) {
if( i != (int) orders[j]){
continue;
}
if(minIndx > j){
minIndx = j;
}
break;
}
}
// System.out.println(String.format("最先出现最多的字符是：'%c'，出现次数：%d", orders[minIndx], max));
return orders[minIndx];
}
- 基于第二种方法的思想，对第三种方法优化。对字符串倒序遍历，遍历一次，记录各个字符出现次数，并记录最大出现次数，及最大次数是的下标。由于是从后往前遍历，记录到最后一个出现最多次数的字符就是最早出现且出现最多的字符。须注意一点，须判断当前字符出现次数大于等于最多次数时，更新最多次数字符及下标时。
public static Character findFirstMaxChar0(@NonNull String str){
int[] nums = new int[MAX_CHAR_INT];
int maxN = 0;
char maxC = str.charAt(0);
for(int i = str.length() - 1; i >= 0; i --){
char c = str.charAt(i);
if(nums[c] > 0){
nums[c] = nums[c] + 1;
} else {
nums[c] = 1;
}
if(nums[c] >= maxN){
maxN = nums[c];
maxC = c;
}
}
// System.out.println(String.format("最先出现最多的字符是：'%c'，出现次数：%d", maxC, maxN));
return maxC;
}
各个方法运行100次的平均运行时间对比如下图所示。
N表示字符串长度，一下时间都是每个方法运行100次得到的平均时间，单位毫秒
两种使用数组的方法运行时间对比
四种方法运行时间对比
结论：
- 使用map的记录字符出现次数的方法运行效率都不高，究其原因，程序中使用了注入“containsKey”、“get”、”put“等方法，乍一看代码只有一行，实际这些方法内部运行了很多其他代码，如hash，遍历entry数组，遍历链表等行为。这些方法内部增加的运行时间复杂度没有被计算在内，因此看上去很简洁的代码实际运行效率并不高；不过从第一个方法到第二个方法的优化还是值得肯定的；
- 使用数组记录字符出现次数的方法效率高，其原因是判断字符第一次出现，及获取字符出现次数的操作都是直接访问数组指定下标，没有其他的附带操作成本；
- 从第三种方法到第四种方法的优化，实际上只优化了程序的可读性，并没有减少程序的运行时间。因为程序最消耗时间的部分是第一步获取字符出现次数及顺序上，优化后的方法恰好是在这一步增加了操作，原本只有对数组的一次读取，一次比较和一次赋值操作，优化后却变成了对数组的一次读取、两次比较、一次赋值。随着数据量的增加多一次比较所造成的时间成本便凸显了出来，因此优化后的程序并没有优化前运行效率高，但可读性却明显高于优化前。在时间成本并没有量级差别时，更应考虑程序的可读性。
