字符串相关算法题。求最优算法。

Question

如何找出一个字符串中出现字符最多的，可能有多个出现最多的字符。
如何找出一个字符串中出现最多的前三个字符。
如果有三个字符出现次数超过字符串长度的1/4如何找出它们。

Answer 1

恩 不考虑效率的话  通解就是把每个字符出现的次数存到HashMap中  然后搞一搞就好了

Answer 2

要高效的算法~~  不用java的库函数。

Answer 3

恩 不考虑效率的话  通解就是把每个字符出现的次数存到HashMap中  然后搞一搞就好了

Answer 4

恩 不考虑效率的话  通解就是把每个字符出现的次数存到HashMap中  然后搞一搞就好了

Answer 5

补充： 采用纯算法来做，不采用java的类库

Answer 6

一次循环！分别建树。
node{string strTemp；int count}s b c r f  。
          s（8）
    b（10）        c（12）
 
最后算一下节点count就看出谁多了估计跟排序好在统计差不太多。这只适合随机性高的数据字符串。

Answer 7

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);

Answer 8

经过测试的
public class Test 
{
public static void main(String [] a)
{
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 (tmp1 == 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 = 1; i < index; i += 2)
{
if (rs[i] > max1)
{
max1 = rs[i];
thePos1 = i;
}
}
rs[thePos1] = -max1;
for (int i = 1; i < index; i += 2)
{
if (rs[i] > max2)
{
max2 = rs[i];
thePos2 = i;
}
}
rs[thePos2] = -max2;
for (int i = 1; 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);
}
}

Answer 9

                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原理差不多

Answer 10

如何超过1/2 这么写效率很高，但是 1/4没有思路，高手来吧public class MoreThanHalf { public static void main(String[] args) {
int count = 0;
String s = "aaaabbbbccccdd";
char c = 0;
int four =0;
for (int i = 0; i < s.length(); i++) {
if (count == 0) {
c = s.charAt(i);
count++;
continue;
}
if (c == s.charAt(i)) {
count++;
} else
count--;
}
System.out.println(c);
}
}

Answer 11

唉....我也玩玩.....
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");
}
}
}

Answer 12

只考虑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).

Answer 13

根据其字符名称建一个hash，字符相同的在同一hash项中

Answer 14

这个算法包含LZ的三个问题，平均用时在 150000 纳秒左右，机子是：笔记本T5500,1G内存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");
}
}
}
}

Answer 15

顺便很邪恶的测试了一下58楼，字符串用的是跟37楼一样的。
出现最多的：a
前三个:a 26  j 10 l 10
时间:600000纳秒左右

Answer 16

回答：如何找出一个字符串中出现最多的前三个字符先给出求解找出一个字符串中出现最多的一个字符算法：一个 int count变量，一个char current变量
int count =1;
char current = a[0];for(int i =1; i < a.length; i++){
 if(current == a[i]){
     count++;
  }else{
     count--;
     if(count == 0){
        current = a[i];
        count++;
     }
   }
}这样到最后current中值就是出现次数最多的字符。然后稍微应用一下，就可以求出 出现次数最多的三个字符。

Answer 17

提供一个比较快的算法，算法复杂度均为 O(字符串长度)：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");
}}