查找字符串中焕毫，出現(xiàn)最先出現(xiàn)最多的字符
查找字符串中最先出現(xiàn)次數(shù)最多的字符沛善。首先需要查找出現(xiàn)次數(shù)最多的字符串航揉，然后查找最多的字符串中出現(xiàn)最早的哪一個(gè)字符。
分析：遍歷字符串即可統(tǒng)計(jì)到各個(gè)字符出現(xiàn)的次數(shù)金刁；統(tǒng)計(jì)最早且最多的字符時(shí)帅涂，一般有兩種思路：
- 記錄各個(gè)字符出現(xiàn)的順序。找到出現(xiàn)最多的次數(shù)后尤蛮，結(jié)合字符出現(xiàn)的順序即可獲取到出現(xiàn)最早的字符媳友；
- 逆序遍歷字符串。順序遍歷一邊不容易查找到最早出現(xiàn)的字符产捞，但是能夠找到最晚出現(xiàn)最多的字符醇锚。所以逆序遍歷字符串，找到最晚出現(xiàn)的字符坯临，那么就找到了最早出現(xiàn)最多次數(shù)的字符了焊唬。
結(jié)合著兩種思路，一般有一下幾種方法實(shí)現(xiàn)看靠。
- 使用map赶促，遍歷兩邊。第一遍挟炬，遍歷字符串?dāng)?shù)組鸥滨， 統(tǒng)計(jì)各個(gè)字符出現(xiàn)的次數(shù)，并記錄出現(xiàn)最多的次數(shù)N谤祖；第二遍婿滓，遍歷字符串，從map中獲取字符出現(xiàn)次數(shù)泊脐，找到第一個(gè)出現(xiàn)次數(shù)為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，逆序遍歷一次容客。逆序遍歷字符數(shù)組秕铛，記錄出現(xiàn)次數(shù)最多的字符C和最多次數(shù)N，由于是逆序遍歷缩挑，最后記錄到的字符就是最早出現(xiàn)且出現(xiàn)次數(shù)最多的字符但两。
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 ;
}
- 使用數(shù)組。首先字符的個(gè)數(shù)是有限的（Character.MAX_VALUE-1個(gè)）供置，可以使用數(shù)組谨湘，使數(shù)組的每個(gè)下標(biāo)對(duì)應(yīng)一個(gè)字符（char和int可以相互抓換），基于這一點(diǎn)可以使用數(shù)組nums來(lái)記錄各個(gè)字符出現(xiàn)的次數(shù)，使用orders數(shù)組記錄各個(gè)字符出現(xiàn)的順序（字符出現(xiàn)次數(shù)為0時(shí)表示第一次出現(xiàn)紧阔，此時(shí)將該字符記錄在orders數(shù)組最后）坊罢。
執(zhí)行步驟：
- 記錄各字符出現(xiàn)次數(shù)及出現(xiàn)順序：通過(guò)一次遍歷即可獲取到所有字符出現(xiàn)的次數(shù)及順序（效率O(n)）；
- 查找出現(xiàn)最多的字符：通過(guò)一次對(duì)nums表的遍歷就能找到最多值max擅耽，同時(shí)記錄對(duì)應(yīng)的下標(biāo)（效率為固定值(Character.MAX_VALUE-1)）活孩；
- 查找出現(xiàn)最早且最多的字符：檢驗(yàn)是否有多個(gè)出現(xiàn)次數(shù)最多的字符（如a/b都出現(xiàn)了100次），找到在orders表里出現(xiàn)最早的乖仇。從第二步中的下標(biāo)開始遍歷nums憾儒，找到出現(xiàn)次數(shù)為max的下標(biāo)，遍歷ordres找到其出現(xiàn)順序（記錄最小下標(biāo)值）乃沙。當(dāng)nums遍歷完成后起趾，記錄到的orders最小下標(biāo)即出現(xiàn)最早的字符。此過(guò)程效率最優(yōu)為1警儒，此時(shí)int值最大的字符出現(xiàn)次數(shù)最多的字符训裆，且第一個(gè)出現(xiàn)；效率最差為log2(n)蜀铲，此時(shí)所有字符出現(xiàn)次數(shù)均相同缭保。
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("最先出現(xiàn)最多的字符是：'%c'，出現(xiàn)次數(shù)：%d", orders[minIndx], max));
return orders[minIndx];
}
- 基于第二種方法的思想蝙茶，對(duì)第三種方法優(yōu)化艺骂。對(duì)字符串倒序遍歷，遍歷一次隆夯，記錄各個(gè)字符出現(xiàn)次數(shù)钳恕，并記錄最大出現(xiàn)次數(shù)，及最大次數(shù)是的下標(biāo)蹄衷。由于是從后往前遍歷忧额，記錄到最后一個(gè)出現(xiàn)最多次數(shù)的字符就是最早出現(xiàn)且出現(xiàn)最多的字符。須注意一點(diǎn)愧口，須判斷當(dāng)前字符出現(xiàn)次數(shù)大于等于最多次數(shù)時(shí)睦番，更新最多次數(shù)字符及下標(biāo)時(shí)。
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("最先出現(xiàn)最多的字符是：'%c'耍属，出現(xiàn)次數(shù)：%d", maxC, maxN));
return maxC;
}
各個(gè)方法運(yùn)行100次的平均運(yùn)行時(shí)間對(duì)比如下圖所示托嚣。
N表示字符串長(zhǎng)度，一下時(shí)間都是每個(gè)方法運(yùn)行100次得到的平均時(shí)間厚骗，單位毫秒
兩種使用數(shù)組的方法運(yùn)行時(shí)間對(duì)比
四種方法運(yùn)行時(shí)間對(duì)比
結(jié)論：
- 使用map的記錄字符出現(xiàn)次數(shù)的方法運(yùn)行效率都不高示启，究其原因，程序中使用了注入“containsKey”领舰、“get”夫嗓、”put“等方法迟螺，乍一看代碼只有一行，實(shí)際這些方法內(nèi)部運(yùn)行了很多其他代碼舍咖，如hash矩父，遍歷entry數(shù)組，遍歷鏈表等行為排霉。這些方法內(nèi)部增加的運(yùn)行時(shí)間復(fù)雜度沒(méi)有被計(jì)算在內(nèi)浙垫，因此看上去很簡(jiǎn)潔的代碼實(shí)際運(yùn)行效率并不高；不過(guò)從第一個(gè)方法到第二個(gè)方法的優(yōu)化還是值得肯定的郑诺；
- 使用數(shù)組記錄字符出現(xiàn)次數(shù)的方法效率高，其原因是判斷字符第一次出現(xiàn)杉武，及獲取字符出現(xiàn)次數(shù)的操作都是直接訪問(wèn)數(shù)組指定下標(biāo)辙诞，沒(méi)有其他的附帶操作成本；
- 從第三種方法到第四種方法的優(yōu)化轻抱，實(shí)際上只優(yōu)化了程序的可讀性飞涂，并沒(méi)有減少程序的運(yùn)行時(shí)間。因?yàn)槌绦蜃钕臅r(shí)間的部分是第一步獲取字符出現(xiàn)次數(shù)及順序上祈搜，優(yōu)化后的方法恰好是在這一步增加了操作较店，原本只有對(duì)數(shù)組的一次讀取，一次比較和一次賦值操作容燕，優(yōu)化后卻變成了對(duì)數(shù)組的一次讀取梁呈、兩次比較、一次賦值蘸秘。隨著數(shù)據(jù)量的增加多一次比較所造成的時(shí)間成本便凸顯了出來(lái)官卡，因此優(yōu)化后的程序并沒(méi)有優(yōu)化前運(yùn)行效率高，但可讀性卻明顯高于優(yōu)化前醋虏。在時(shí)間成本并沒(méi)有量級(jí)差別時(shí)寻咒，更應(yīng)考慮程序的可讀性。
