[其它] Quant interview的一道编程题 [推广有奖]

11楼

blackwood_li 发表于 2009-10-17 08:31:12

已经考虑到了各种情况了，每个数必然出现2次的情况是当已经有2个数字只出现1次或者有一个数字出现0次后发生的情况，比如剩下9个数字，18位数，要使每个数字出现小于3次，那么必然是每个都出现2次。

这个算法的时间复杂度应该是（n*m），运算量不大，主要是并没有去真正把每个数找出来，而是通过排列组合的一些知识直接进行了一些运算。

我开始以为是小于3了，不超过3的话改下代码就可以了。顺便简化下代码和修改下注释。注意结果需要再乘以0.9。
long count（int n，int m）{
if(m>3n) {
return 0；//这样必然出现4个以上的重复数字。
}
else if (n==1) {
return 1;
} else
return count(n-1,m)+m*count(n-1,m-1)+m*(m-1)/2*count(n-1,m-2)+m*(m-1)*(m-2)/6*count(n-1,m-3);//分别计算每个数字出现0次1次2次3次的情况然后相加。
}