字符串相关算法题。求最优算法。
如何找出一个字符串中出现字符最多的，可能有多个出现最多的字符。
如何找出一个字符串中出现最多的前三个字符。
如果有三个字符出现次数超过字符串长度的1/4如何找出它们。
[解决办法]
- Java code
String str = "aglakjsflajfla;sfdjalsfjal;sjfdlasjfdljsafljasljflasfj";char [] strArray = str.toCharArray();int [] rs = new int[strArray.length * 2];int index = 0;for (int i = 0; i < strArray.length; i++){ char tmp1 = strArray[i]; if (c == 0) { continue; } rs[index++] = tmp1; rs[index] = 1; for (int j = i + 1; j < strArray.length; j++) { char tmp2 = strArray[j]; if (tmp2 == 0) { continue; } if (tmp1 == tmp2) { strArray[j] = 0; rs[index]++; } } index++;}int max1 = 0;int max2 = 0;int max3 = 0;int thePos1 = 0;int thePos2 = 0;int thePos3 = 0;for (int i = 0; i < index; i += 2){ if (rs[i] > max1) { max1 = rs[i]; thePos1 = i; }}rs[thePos1] = -max1;for (int i = 0; i < index; i += 2){ if (rs[i] > max2) { max2 = rs[i]; thePos2 = i; }}rs[thePos2] = -max2;for (int i = 0; i < index; i += 2){ if (rs[i] > max3) { max3 = rs[i]; thePos3 = i; }}System.out.println("No1. " + (char)rs[thePos1 - 1] + ":" + max1);System.out.println("No2. " + (char)rs[thePos2 - 1] + ":" + max2);System.out.println("No3. " + (char)rs[thePos3 - 1] + ":" + max3);
[解决办法]
String str = "aglakjsflajfla;sfdjalsfjal;sjfdlasjfdljsafljasljflasfj";
char[] strArray = str.toCharArray();
int[] charCount = new int[1000];
for(int i = 0; i < strArray.length; i++)
{
int value = (int)strArray[i];
charCount[value] += 1;
}
for(int i = 0; i < strArray.length; i++)
{
int value = (int)strArray[i];
System.out.print(strArray[i]);
System.out.print(":");
System.out.println(charCount[value]);
}
基本原理如下：遍历字符数组strArray，将字符转换成整数，如A就是65？97？。
然后用这样一个整数作为下标，将该字符出现的次数记录在整形数组charCount中，charCount[65]就是A出现的次数了。
和前面提到的hashtable原理差不多
[解决办法]
唉....我也玩玩.....
import java.util.Comparator;
import java.util.TreeMap;
import java.util.TreeSet;
class Parent implements Comparator<String>{
@Override
public int compare(String o1, String o2) {
if(o1.equals(o2)){
return 0;
}else if(Integer.parseInt(o1.substring(0,o1.length()-1))>Integer.parseInt(o2.substring(0,o2.length()-1))){
return 1;
}
return -1;
}
}
public class Child {
public static void main(String[] args) {
int count;
String[] st;
String s = "shldg./asm'aoaayaaaypwy3u2.......0373902...tSk'al'f,askr[auirp0au2q6";
TreeSet<String> set = new TreeSet<String>(new Parent());
TreeMap<Character,Integer> map = new TreeMap<Character,Integer>();
for(char c:s.toCharArray()){
if(map.get(c) == null){
map.put(c, 1);
}else{
count = map.get(c)+1;
map.put(c, count);
}
}
for(Character c:map.keySet()){
set.add(""+map.get(c)+c);
}
st = set.toArray(new String[0]);
count = 0;
System.out.print("出现最多的字符:"+st[st.length-1].charAt(st[st.length-1].length()-1));
for(int i = st.length-2;i>=0;i--){
if(st[i].charAt(0) == st[i+1].charAt(0)){
System.out.print(" "+st[i].charAt(1));
}else{
break;
}
}
System.out.println();
System.out.println("出现最多的前三个字符：");
for(int i = st.length-1;i>=0;i--){
if(i>st.length-4){
System.out.println(st[i].substring(st[i].length()-1)+" : "+st[i].substring(0,st[i].length()-1));
if(Integer.parseInt(st[i].substring(0,st[i].length()-1))>s.length()*0.25){
count += 1;
}
}else if(st[i].substring(0,st[i].length()-1).equals(st[i+1].substring(0,st[i].length()-1))){
if(i == st.length-4){
System.out.print("与出现次数最多的第三个字符次数相等的还有："+st[i].charAt(st[i].length()-1));
}else{
System.out.print(" "+st[i].charAt(st[i].length()-1));
}
}else{
System.out.println();
break;
}
}
if(count == 3){
System.out.println("有三个字符出现次数总和超过字符串长度的1/4：:-D");
}
}
}
[解决办法]
只考虑ASCII码在0～127之间的字符（由于128～255之间的字符出现比较少，就暂不考虑，不然影响快速排序的效率）
建立整型数组count，用于记录字符串中各字符出现次数，遍历字符串,复杂度为O(n)。
int count = new int[128*2];
数组count解释为
struct
{
int charID; //字符的ASC码
int charCount;//字符串中字符出现的次数
}
再利用快速排序法，根据charID非递增排序count数组，最后比较count数组的前几项即可，复杂度为O(nlogn)。
所以整体的复杂度为O(nlogn).
[解决办法]
这个算法包含LZ的三个问题，平均用时在 150000 纳秒左右，机子是：笔记本T5500,1G内存
- Java code
public class Test{public static void main(String[] args){ String str = "aglakjsflajfla;sfdjalaaaaaaaaasfjal;sjfdlaaaaaaaasjfdljsafljasljflasfj"; long start = System.nanoTime(); char[] strArray = str.toCharArray(); int[] count = new int[]{1,1,1} ; String[] maxChar = new String[]{String.valueOf(strArray[0]),String.valueOf(strArray[0]),String.valueOf(strArray[0])} ; for(int index = 0 ; index < strArray.length ; index ++){ char key = strArray[index] ; int temp = 1; for(int i = index+1 ;i < strArray.length;i++){ if( key == strArray[i] ){ index++ ; temp++ ; if((i - 1) > index){ strArray[i] = strArray[index] ; strArray[index] = key ; } } } if(temp >= count[2] && temp < count[1]){ if(temp == count[2]){ maxChar[2] += " " + String.valueOf(key) ; continue ; } maxChar[2] = String.valueOf(key) ; count[2] = temp ; }else if(temp >= count[1] && temp < count[0]){ if(temp == count[1]){ maxChar[1] += " " + String.valueOf(key) ; continue ; } maxChar[2] = maxChar[1] ; count[2] = count[1] ; maxChar[1] = String.valueOf(key) ; count[1] = temp ; }else if(temp >= count[0]){ if(temp == count[0]){ maxChar[0] += " " + String.valueOf(key) ; continue ; } count[2] = count[1] ; maxChar[2] = maxChar[1] ; count[1] = count[0] ; maxChar[1] = maxChar[0] ; count[0] = temp ; maxChar[0] = String.valueOf(key) ; } } System.out.println(System.nanoTime() - start); for(int i =0 ; i<3 ; i++){ System.out.println(maxChar[i] + " :" + count[i]); if(count[i] > strArray.length/4){ System.out.println(maxChar[i] + "超过了字符串长度的1/4"); } } }}
[解决办法]
提供一个比较快的算法，算法复杂度均为 O(字符串长度)：
- Java code
public class StringMax { /** * 如何找出一个字符串中出现字符最多的，可能有多个出现最多的字符。 * @param src */ public static void no1(String src){ System.out.println("找出一个字符串中出现字符最多的"); System.out.println("源字符串："+src); long begin=System.nanoTime(); char[] srcCharArr=src.toCharArray(); //此处只考虑了ASCII字符； //如果有双字节字符，则用int[] count=new int[65536]; //JAVA的数组会初始化，会比较耗费时间。如果src不长，这样做可能会得不偿失 int[] count=new int[128]; int max=0; int maxcount=0; char[] cr=new char[src.length()]; for (int i=0;i<srcCharArr.length;i++){ int t=++count[srcCharArr[i]]; if (t>max){ max=t; maxcount=0; cr[maxcount]=srcCharArr[i]; } else if (t==max){ cr[++maxcount]=srcCharArr[i]; } } long usetime=System.nanoTime()-begin; System.out.println("字符出现最多次数："+max+"\n包括:"); for (int i=0;i<=maxcount;i++){ System.out.print(cr[i]+" "); } System.out.println("\n共"+(maxcount+1)+"个"); System.out.println("共耗时："+usetime+"ns"); } /** * 如何找出一个字符串中出现最多的前三个字符。 * @param src */ public static void no1to3(String src){ System.out.println("找出一个字符串中出现最多的前三个字符。"); System.out.println("源字符串："+src); long begin=System.nanoTime(); char[] srcCharArr=src.toCharArray(); int[] count=new int[128]; int[] max={0,0,0}; char[] maxChar={0,0,0}; for (int i=0;i<srcCharArr.length;i++){ int t=++count[srcCharArr[i]]; int min=max[0]<max[1]?(max[0]<max[2]?0:2):(max[1]<max[2]?1:2); if (t>max[min]){ if (srcCharArr[i]==maxChar[0]){ max[0]=t; } else if (srcCharArr[i]==maxChar[1]){ max[1]=t; } else if (srcCharArr[i]==maxChar[2]){ max[2]=t; } else { max[min]=t; maxChar[min]=srcCharArr[i]; } } } long usetime=System.nanoTime()-begin; System.out.println("字符串中出现最多的前三个字符："); for (int i=0;i<3;i++){ System.out.print(maxChar[i]+"["+max[i]+"]次 "); } System.out.println("\n共耗时："+usetime+"ns"); } /** * 如果有三个字符出现次数超过字符串长度的1/4如何找出它们。 * @param src */ public static void sumMax3(String src){ //参照no1to3的做法，找到最多的3个字符，然后sum，如果>=src.length()，就找到了 } public static void main(String[] args) { // TODO Auto-generated method stub no1("aglakjsflajfla;sfdjalaaaaaaaaasfjal;sjfdlaaaaaaaasjfdljsafljasljflasfj"); no1to3("aglakjsflajfla;sfdjalaaaaaaaaasfjal;sjfdlaaaaaaaasjfdljsafljasljflasfj"); }}