腾讯前端笔试题

今天在网上看到一条腾讯的前端笔试题，大家看看有啥思路：
“几个字符串组成的数组["abcaaabbc","eaeaebe","cbacccc",...]等等，个数不限制，那么要求对这个数组排序，排序规则就是最多出现字符的次数升序排序，遇到相等的情况就对比第二多字符出现字数，依次类推。
那么上述的三个例子排序出来是：“cbacccc”（c出现5次）、“abcaaabbc”、“eaeaebe”（虽然出现最高次字符都是4次，但是第二个第二高的b出现了3次，比第三个第二高的a出现的2次高）。写一个函数实现上述功能”
 

16 个解决方案

#1

发现自己真的好闲。闲到蛋疼。。。。。抛砖引玉吧

Array.prototype.inArray=function (value){for (var i=0;i<this.length;i++){if (this[i] == value){return true;}}return false};
function arrSort(){
    this.arr=["abcaaabbc","eaeaebe","cbacccce","ddda","eeeea","fffffaa",'abcdefghijklmnopqrstuvwxyzzzz'];
    this.getArrayByCharCount=function(){
        var countArr=new Array();
        for(var i=0;i<this.arr.length;i++){
            countArr[i]=[];
            var chrArr=new Array();
            var chr=this.arr[i].split('');
            for(var j=0;j<chr.length;j++){
                if(!chrArr.inArray(chr[j])){
                    chrArr.push(chr[j]);
                    countArr[i].push(this.arr[i].split(chr[j]).length-1);//统计当前字母出现次数
                }
            };
            countArr[i].index=i;//标识原数组序列
        };
        return countArr;
    };
    this.showSortResult=function(){
        var arr=this.getArrayByCharCount();
        arr.sort(function(a,b){
            a.sort(function(a,b){return b-a});
            b.sort(function(a,b){return b-a});
            var str='';
            var o=a.length>b.length?b:a;
            for(var i=0;i<o.length;i++){
                str+=str.length==0?b[i]-a[i]:' || '+(b[i]-a[i]);
            };
            return eval(str);
        });
        var res='';
        for(var i=0;i<arr.length;i++){
            res+=res.length==0?'['+this.arr[arr[i].index]+']':',['+this.arr[arr[i].index]+']';
        }
        alert("最终排序为："+res);
    }
};
var as=new arrSort();
as.showSortResult();

#2

搞了个随机数组测试效率，也改了下效果展示方式，200个数组，每个数组字符长度15。

<script type="text/javascript">
function getArrByRandom(){
    var seed = new Array( 'a','b','c','d','e','f','g','h','i','j','k','m','n','p','Q','r','s','t','u','v','w','x','y','z');
    seedlength = seed.length;
    var a = '';
    for (var i=0;i<15;i++) {
        j = Math.floor(Math.random()*seedlength);
        a += seed[j];
    }
    return a;
}

var randomArray=new Array();
for(var i=0;i<200;i++){
    randomArray.push(getArrByRandom());
};

Array.prototype.inArray=function (value){for (var i=0;i<this.length;i++){if (this[i] == value){return true;}}return false};
function arrSort(){
    this.arr=randomArray;
    this.getArrayByCharCount=function(){
        var countArr=new Array();
        for(var i=0;i<this.arr.length;i++){
            countArr[i]=[];
            var chrArr=new Array();
            var chr=this.arr[i].split('');
            for(var j=0;j<chr.length;j++){
                if(!chrArr.inArray(chr[j])){
                    chrArr.push(chr[j]);
                    countArr[i].push(this.arr[i].split(chr[j]).length-1);//统计当前字母出现次数
                }
            };
            countArr[i].index=i;//标识原数组序列
        };
        return countArr;
    };
    this.showSortResult=function(){
        var arr=this.getArrayByCharCount();
        arr.sort(function(a,b){
            a.sort(function(a,b){return b-a});
            b.sort(function(a,b){return b-a});
            var str='';
            var o=a.length>b.length?b:a;
            for(var i=0;i<o.length;i++){
                str+=str.length==0?b[i]-a[i]:' || '+(b[i]-a[i]);
            };
            return eval(str);
        });
        var res='';
        for(var i=0;i<arr.length;i++){
            res+='['+this.arr[arr[i].index]+']:"'+arr[i]+'"\n'
        }
        document.getElementById('arrsort').value="最终排序为：\n"+res;
    }
};
window.onload=function(){
    var as=new arrSort();
    as.showSortResult();
}

</script>
<textarea  rows="30" cols="60" id="arrsort"></textarea>

#3

砖来了。。

<script type="text/javascript">
	var string = ["zzzz","ccewcwefg","cbacccccc", "zxcv........"];
	var strLength = [];
	for(var i in string)
	{
		var maxLength = 0;
		var maxChar = '';
		for(var j in string[i])
		{
			var len = string[i].split(string[i][j]).length-1;
			if(string[i][j] != maxChar && len >= maxLength)
			{
				maxChar = string[i][j];
				maxLength = len;
			}
		}
		strLength[i] = [maxLength, i];
	}
	var len1 = strLength.length - 1;
	for(var i=0;i<len1; ++i)
	{
		var len2 = strLength.length;
		for(var j=i+1; j<len2; ++j)
		{
			if(strLength[i][0] < strLength[j][0])
			{
				var temp = strLength[i];
				strLength[i] = strLength[j];
				strLength[j] = temp;
			}
		}
	}
	var str = '';
	for(var i in strLength)
	{
		str += string[strLength[i][1]]+'\n';
	}
	alert(str);
</script>

#4

板砖来了：

     var array = ['abcaaabbc','aeaebbaebe','cbacccc','zzzyhhhhhhhiiiiii'];
        var revert = [];
        function sortby(a,b){
            var revertA = trans(a);
            var revertB = trans(b);
            return revertA < revertB;
            
            function trans(arr){
                var revert = [];
                for(var i in arr){
                    var q = arr.split(eval("/[^"+arr[i]+"]/g")).join('').length;
                    revert.push(q);
                }
                revert.sort();
                revert.reverse();
                console.debug(revert);
                return revert;
            }
        }
        array.sort(sortby);
        console.debug(array,9999);

#5

搞了好久，对比了两种算法：
1、一种是类似于2楼的，把原数组转化为可得到正确结果的数字数组B，对数组B排序后得到顺序，映射给原数组。
2、写一个sortby回调函数
测了下，第一种算法的性能较好。在转化数字数组B的时候，要注意控制，遍历过个数的字符就不要再遍历了；

下面是主要代码：
1、

        var array = ['abcaaabbc','aeaebbaebe','cbacccc','zzzyhhhhhhhiiiiii'];
        var revert = [];

        var start = new Date().getTime();//start time 
        function charSort(array, revert){
            for(var i in array){
                var obj = {};
                for(var j in array[i]){
                    obj[array[i][j]] = '';
                }
                var k=[];
                for(var m in obj){
                    k.push(m);
                }
                var subrevert = [];
                for(var j in k){
                    var q = array[i].match(eval("/"+k[j]+"/g")).length;
                    subrevert.push(q);
                }
                subrevert.sort(function(m,n){
                    return m<n;
                });
                subrevert.index = i;
                revert.push(subrevert);
            }
            revert.sort();
            revert.reverse();
            var arraymirror = [];
            for(var i in revert){
                arraymirror[revert[i].index] = array[i];
            }
            array = arraymirror
            return array;
        }      
       
        charSort(array, revert);
        var end = new Date().getTime();
        document.write((end-start) + '<br />');
        console.debug(array);

2、

        var array = ['abcaaabbc','aeaebbaebe','cbacccc','zzzyhhhhhhhiiiiii'];
        function sortby(a,b){
            var revertA = trans(a,[]);
            var revertB = trans(b,[]);
            return revertA < revertB;    
        }
        function trans(arr, revert){
            var obj = {};
            for(var i in arr){
                obj[arr[i]] = '';
            }
            var k=[];
            for(var i in obj){
                k.push(i);
            }
            for(var i=0; i<k.length; i++){
                var q = arr.match(eval("/"+k[i]+"/g")).length;
                revert.push(q);
            }
            revert.sort(function(m,n){
                return m<n;
            });
            return revert;
        }
        var start = new Date().getTime();
        array.sort(sortby);
        var end = new Date().getTime();
        document.write((end-start) + '<br />');
        console.debug(array,9999);

折腾过程中，想起大学那会，数据结构老师纠结各种查找算法，现在看来是多么有用。怎样用好循环，是很值得研究的事情。

#6

呵呵，你对自己写的代码，有测试的么？？？

#7

引用 1 楼  的回复:

发现自己真的好闲。闲到蛋疼。。。。。抛砖引玉吧

那还不好啊...

#8

var arr = ["abcaaabbc","eaeaebe","cbacccc"];
//var arr = ["bcd","bbc","aad","ccab"];

arr.sort(function(a,b)
{
	var m = repeat(a), n=repeat(b), min = Math.min(m.length, n.length);
	function repeat(str)
	{
		var r = str.split('').sort().join('').match(/(.)\1*/g);
		return r.sort(function(a,b){return b.length-a.length})
	}
	for (var i=0; i<min; i++)
	{
		var x = m[i].length, y = n[i].length;
		if (x !== y) return y - x;
	}
	return 0; // 类似 ["bbc","aad","ccab"] 规则不明无法编码
});

console.log(arr);

性能上或许比5楼大大的好一点

#9

引用 8 楼  的回复:

JScript code
var arr = ["abcaaabbc","eaeaebe","cbacccc"];
//var arr = ["bcd","bbc","aad","ccab"];

arr.sort(function(a,b)
{
    var m = repeat(a), n=repeat(b), min = Math.min(m.length, n.length);
  ……

内嵌函数正则改改，不重复的字符就不要了：

	function repeat(str)
	{
		var r = str.split('').sort().join('').match(/(.)\1+/g);
		return r ? r.sort(function(a,b){return b.length-a.length}) : []
	}

外面判断一下min==0的情况。

#10

引用 9 楼  的回复:

引用 8 楼  的回复:

JScript code
var arr = ["abcaaabbc","eaeaebe","cbacccc"];
//var arr = ["bcd","bbc","aad","ccab"];

arr.sort(function(a,b)
{
var m = repeat(a), n=repeat(b), min = Math.min(m.leng……

今早看了下，我的问题很大呀！！！
之前我都不敢用console.debug来输出，firebug直接崩溃。看来有很多地方值得改进哟！

#11

事实证明，不开启firebug等调试器的时候，我的第一种方案速度和8楼的是在一个量级上的。
不知道开启firebug的时候为什么那么慢。

#12

引用 11 楼  的回复:

事实证明，不开启firebug等调试器的时候，我的第一种方案速度和8楼的是在一个量级上的。
不知道开启firebug的时候为什么那么慢。

问题是：
你两种方法 在IE中我都得不到正确的排序结果

#13

Vidor 对正则的用法很是有点熟然于心的意思
看另一个贴子求解字符串长度的用法也很是巧妙，这里对字符归类的应用也很是巧妙呀

赞一个。对正则一向是一知半解的，简单点的倒好说。复杂型的我得搞老长时间。。。。。

#14

8楼代码瞬间把我折服了！

获得了一点点体会：
1、明明有length属性可以直接判断；我却新建了数组来放这个length，这个应该是开销比较大的
2、除了sortby回调本身要参与循环之外，在回调函数里面，只有一个主要循环；而我有好几个循环呢，重复的遍历，开销也很大。这应该是算法上的累赘。
3、尽量减少循环的次数，无论是Math.min(m.length, n.length);还是r ? r.sort(function(a,b){return b.length-a.length}) : []都是为了减少循环次数；我记得我在当时是有想到，可是么有做到。
4、str.split('').sort().join('').match(/(.)\1*/g);这样获得关键序列的方式很优雅，相比之下，我的方法很拙劣。

嗯，能想到的就这些了。以后做这样的算法题，一开始的思考比后来的千辛万苦优化更重要。

#15

引用 12 楼  的回复:

引用 11 楼  的回复:
事实证明，不开启firebug等调试器的时候，我的第一种方案速度和8楼的是在一个量级上的。
不知道开启firebug的时候为什么那么慢。

问题是：
你两种方法在IE中我都得不到正确的排序结果

是因为用for in循环了数组的缘故。IE不支持。

#16

引用 14 楼  的回复:

8楼代码瞬间把我折服了！

获得了一点点体会：
1、明明有length属性可以直接判断；我却新建了数组来放这个length，这个应该是开销比较大的
2、除了sortby回调本身要参与循环之外，在回调函数里面，只有一个主要循环；而我有好几个循环呢，重复的遍历，开销也很大。这应该是算法上的累赘。
3、尽量减少循环的次数，无论是Math.min(m.length, n.length);还是r……

不要这么说，互相学习，其实我很菜的。

重复字符统计，基本上两种方法（我的水平想不出第三种），键值映射或正则。
键值映射应该优于正则，str.split('').sort().join('').match(/(.)\1+/g) 内部实现循环不会少。

我测试了一下：

function byRepeat(a,b)
{
	var m = repeat(a), n=repeat(b), min = Math.min(m.length, n.length), max = Math.max(m.length, n.length);
	function repeat(str)
	{
		var a=[], o={}, len=str.length;
		for (var i=0; i<len; i++) // 键-值映射
		{
			var s=str.charAt(i); // 比 substr(i,1) 快点
			// 第二次出现再push()
			!(s in o) ? o[s]=undefined : (o[s]==undefined) ? (o[s]=a.length, a.push(2)) : a[o[s]]++;
		}
		return a.sort(function(a,b){b-a});
	}
	for (var i=0; i<min; i++)
	{
		if (m[i] !== n[i]) return n[i] - m[i];
	}
	if (min!=max) return m.length==max ? -1 : 1;
	return 0;
}

var arr = ["abcaaabbc","eaeaebe","cbacccc"];
arr.sort(byRepeat);
console.log(arr);

Firefox、Chrome有明显提升，IE9反而略逊于正则。总体表现Chrome最差，IE9最好。