“给定一个字符串,找出这个字符串中出现最多的字符和次数”,笔试碰到的一个问题,还是比较简单的,贴出来与大家分享。
public class CharCount { public static void Charcount(String string) { if (string == null) return; int[] count = new int[string.length()]; for (int i = 0; i < count.length; i++) { // 将字符串中索引字符存在临时变量中 char mid = string.charAt(i); for (int j = 0; j < count.length; j++) { if (mid == string.charAt(j)) count[i]++; } } // 得到次数最多的字符 int index = 0; int max = count[0]; for (int i = 0; i < count.length; i++) { if (max < count[i]) { max = count[i]; index = i; } } System.out.println(); System.out.println("字符=" + string.charAt(index)); System.out.println("次数=" + count[index]); } public static void main(String[] args) { Charcount("ABAACGDHGSTHJHH"); } }
上面的这算法当中有两个for 的嵌套循环 还有一个 for 循环的得到次数最多字符的操作。时间复杂度也不难得到是O(n^2).
如果遇到数据量比较大的,上述这个算法还是有点不尽人意。
如果在给定字符串的时候,就将字符串中出现的字符都保存起来,这里所说的字符是只要出现一次,不管出现几次值保存一次,然后按照这个保存起来的表,对字符串来 for 的嵌套循环,应该会节约时间,遇到出现的字符不多,但字符串很长的时候,能够节省大把的时间。
import java.util.ArrayList; public class CharCount { public static void Charcount(String string) { //ArrayList 保存字符串中出现的字符 ArrayList list=new ArrayList(string.length()); for(int i=0;i<string.length();i++){ //只要表中不包含,将它添加到表中 if(!list.contains(string.charAt(i))){ list.add(string.charAt(i)); } } int[] count = new int[list.size()]; //这里外循环就不用遍历整个字符串,仅仅按照List表中所保存的字符进行遍历 for(int i=0;i<list.size();i++){ char mid=(Character) list.get(i); for(int j=0;j<string.length();j++){ if(mid==string.charAt(j)){ count[i]++; } } } int index = 0; int max = count[0]; for (int i = 0; i < count.length; i++) { if (max < count[i]) { max = count[i]; index = i; } } System.out.println("字符串中出现的字符:"); for(int k=0;k<list.size();k++) { System.out.print(list.get(k)+" "); } System.out.println(); System.out.println("字符" + list.get(index)+"出现的次数最多"); System.out.println("共出现次数为: " + count[index]); } public static void main(String[] args) { Charcount("ABAACGDHGSTHJHH"); } }
作者:Orson
出处:http://www.cnblogs.com/java-class/
如果,您认为阅读这篇博客让您有些收获,不妨点击一下右下角的【推荐】
如果,您希望更容易地发现我的新博客,不妨点击一下左下角的【关注我】
如果,您对我的博客内容感兴趣,请继续关注我的后续博客,我是【Orson】
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段 声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
转载:http://www.cnblogs.com/java-class/archive/2013/04/25/3043444.html