web前端笔试一道面试题目新解

算出字符串中出现次数最多的字符是什么，出现了多少次
据说是百度的，个人认为百度公司的题目没有这么简单
这不知道是哪位网友给出的回答，答案是对的，但显然不要这么复杂！！

<script type=”text/javascript”>
//<![CDATA[var str ="adadfdfseffserfefsefseeffffftsdg"; //命名一个变量放置给出的字符串
var maxLength = 0; //命名一个变量放置字母出现的最高次数并初始化为0
var result = ''; //命名一个变量放置结果输入

while( str != '' ){ //循环迭代开始，并判断字符串是否为空
oldStr = str; //将原始的字符串变量赋值给新变量
getStr = str.substr(0,1); //用字符串的substr的方法得到第一个字符（首字母）
eval("str = str.replace(/"+getStr+"/g,'')"); //详细如补充

if( oldStr.length-str.length > maxLength )
{ //判断原始的字符串的长度减去替代后字符串长度是否大于之前出现的最大的字符串长度
maxLength = oldStr.length-str.length; //两字符串长度相减得到最大的字符串长度
result = getStr + "=" + maxLength //返回最大的字符串结果（字母、出现次数）
}
}

alert(result) //弹出结果
//]]>
</script>

我的解答：

	<script>
	var str = "adadfdfseffserfefsefseeffffftsdg"; //命名一个变量放置给出的字符串
	var result = {};
	for ( var i = 0; i < str.length; i++) {
		var c = str.charAt(i);
		if (result[c]) {
			result[c]++;
		} else {
			result[c] = 1;
		}
	}
	console.log(result);
	var max=0;
	var maxChar='';
	for ( var key in result) {
		if(result[key]>max){
			max=result[key];
			maxChar=key;
		}
	}
	console.log(maxChar);
	console.log(max);
</script>

评论

23 楼 flyer646 2010-12-13  

楼主 的效率低 （网友给的效率高一些，每个字符只做一次） 假如这个字符串很长的话 你循环就很多次 ，

22 楼 liuzhiqiangruc 2010-12-10  

z_joey 写道

用正则表达式的那个算法效率太低了吧

哪种用正则的方式也不失为一种好方法，是一种不错的思路。

21 楼 liuzhiqiangruc 2010-12-10  

针对该问题，有两种解法，无非就是时间和空间的权衡，在实际应用中根据具体情况而定，具体代码就不写了，分析如下，感兴趣的欢迎PK。

第一种解法，牺牲时间换取空间，具体做法是：
1，首先对字符串进行排序，这一步的时间复杂度是固定的。可以有多种排序算法选择。
2，扫描排序后字符串，并且统计遇到的每个字符的数量。方法为：如果下一个字符和当前字符不一致，则当前统计到的数据就是该字符在字符串中出现的次数，此时拿该数据与之前出现过的最大的数据进行比较。
3，扫面结束之后即可以得到出现次数最多的字符，以及出现的次数。
在此过程中空间复杂度为：3，排序时候的空间复杂度为1，扫描阶段需要记录当前字符，当前字符出现的次数，以及曾经出现的最多字符的出现次数。


第二种解法，牺牲空间换取时间，具体做法是：
1，不排序，直接扫描字符串，每遇到一个之前没遇到的字符就把它记下来，并设置其出现的次数为1，如果之前出现，则将该字符的出现次数加1.
2，在每扫描一个字符，并且得到该字符出现的次数时，就与最大的一个次数比较，得到新的最大的次数和字符。
3，扫描结束之后也就得到了结果

这个过程中只需要遍历字符串一次，时间复杂度是线性的，空间复杂度为（字符串中出现的不同的字符串的次数+1）*2.

--有疑问请继续跟帖。

20 楼 z_joey 2010-12-10  

用正则表达式的那个算法效率太低了吧

19 楼 drcjian 2010-12-10  

把字符串放到hashtable中(字符串作为主键，添加的时候遇到已经存在的主键则改变其值，否则重新添加)

18 楼 superobin 2010-12-09  

呵呵。。我这有个比较另类的写法：一句话。呵呵。。不要考虑效率，就是玩儿。有个缺陷就是不支持换行，不过，玩嘛。。

alert("asdfsooafwqefwefvl;zxkjv;lxcvj;ljslfasjowqincvowqnvphsdfohbonodujsdaopfijwqoeifjwef"
.split("").sort().join("")
.replace(/(.)\1*/g,function(t){
	return t.length+"@"+t.charAt(0)+"\0"
}).split("\0").sort(function(a,b){
	return a.split("@")[0]>b.split("@")[0]?-1:1
}).join(",").replace(/(\d+)@.(,\1@.)*/g,function(t) {
	return t.split("@")[0]+"@"+t.replace(/,?\d+@/g,"")
}).split(/,\d+@/g)[0].replace(/(\d+)@(.+)/,function(t,a,b) {
	return "最多的字符为:"+b.split("").join("、")+",共"+a+"个";
}));

结果是：
最多的字符为:f、o,共9个

17 楼 cuixiping 2010-12-09  

建议搞一个超长的字符串，比如十万个字符，用各家的算法比比效率

16 楼 satanultra 2010-12-09  

				var chArr ="adadfdfseffserfefsefseeffffftsdg".split("");
				var hashList = {};
				var result = [chArr[0], 1];
				for(var i=1;i<chArr.length;++i)
				{
					if(!hashList[chArr[i]])
						hashList[chArr[i]] = 0;
					if(++ hashList[chArr[i]]  > result[1])
						result = [chArr[i], hashList[chArr[i]]];
				}
				alert(result);

15 楼 vb2005xu 2010-12-09  

我也来凑个热闹,应该考虑到次数最多的可能有好几个字符吧

	// 算出字符串中出现次数最多的字符是什么，出现了多少次 
	function calcSTR(str){
		var a = [] ;
		str.replace(/ /g,'').replace(/./g ,function(c){	
			a[c] = a[c] ? a[c] + 1 : 1 ;
		});	
		console.log("每个字符出现的个数: ",a);
		var max = 0 ;
		var cr = '' ;
		for(var p in a){
			if (a[p]>max){max = a[p];cr = p ;}
			else if (a[p]==max)
				cr+=' '+p;				
		}
		console.log("出现次数最多的字符: [%s],出现的次数: [%d]",cr,max);
		
	};
	calcSTR("SADASDASD SADASDASdsfdsD asdassHHSHDHASHDHAS");

14 楼 niuxg 2010-12-08  

<script>
var a = "";
var maxValue = 0;
var str = "adadseffouyangpingfsffffftsdg";
while(str.length>0){
    l = str.length;
    s = str.charAt(0);
    str = str.replace(eval("/"+s+"/g"),"");
    if(maxValue<(l-str.length)){
        a = s;
        maxValue=l-str.length;
    }
}
alert(a + maxValue);
</script>

13 楼 tuohaif1 2010-12-08  

jdomyth 写道

好像没人考虑所有字母个数一样的情况。

我也这么想地

12 楼 luobin23628 2010-12-08  

楼主没有考虑中文和特殊字符

11 楼 edisonlz 2010-12-08  

hash 一下，在记录一下max 一次循环应该就哦了

10 楼 jdomyth 2010-12-08  

好像没人考虑所有字母个数一样的情况。

9 楼 binlaniua 2010-12-07  

厄 不好意思 用数组的画 下标不好获取了
还是用对象波

var a = {};
var maxValue = 0;
var str = "adadseffouyangpingfsffffftsdg";
str.replace(/./g, function(c){
     var count = a[c] ? a[c] : 1;
     a[c] = count + 1;
     maxValue = maxValue < a[c]? a[c] : maxValue;
     return '';
});
for(var p in a){
   if(a[p] == maxValue){
     alert(p + '\t' + maxValue);
     break;
   }
}

8 楼 binlaniua 2010-12-07  

var a = [];
var str = "adadseffouyangpingfsffffftsdg";
str.replace(/./g, function(c){
     var count = a[c] ? a[c] : 1;
     a[c] = count + 1;
     return '';
});

7 楼 javaFisher 2010-12-07  

2L 和 3L 的把查询最大值放到一次循环中了。更好
少了一次循环

6 楼 javaFisher 2010-12-07  

看到帖子，自己写了个。居然和LZ的如此雷同

<script type="text/javascript">
//<![CDATA[
var s = 'adadfdfseffserfefsefseeffffftsdg' ;
var a = s.split('') ;
var a_new = [] ;
for (var i = 0, le = a.length ; i < le; i++ ) {
    if (a_new[a[i]]){
        a_new[a[i]]++;
    }else {
        a_new[a[i]] = 1 ;
    }
}
var max = 0 ;
var maxS = '' ;
for (var i in a_new) {
    if (a_new[i] > max){
        max = a_new[i] ;
        maxS = i ;
    }
}
//]]>
</script>

5 楼 EldonReturn 2010-12-06  

桶式排序么？

4 楼 hyj1254 2010-12-06  

linux1689 写道

面试前为啥不看看《编写高质量代码：Web前端开发修炼之道》和《大巧不工：Web前端设计修炼之道》呢？

受楼上的指点，特意去浏览了下第一本，书是好书，但跟本贴关系不大。