传说是Tencent面试题~~~

Question

给定正整数n, 
求所有数组a[n],满足: 
a[i]等于a[n]中 i 的个数. 
要求时间复杂度为O(n^2),最好为O(1) 如: 
n=4时,a[n]= 
{1,2,1,0} (说明:a[4]中有1个0,2个1,1个2) 
{2,0,2,0} 

Answer 1

如果a[n]中的数都不大于n-1;你可以设一个与a[n]一样的大的数组sum[n],用来统计各个值出现的次数.
for(int i=0;i<a.length;i++) sum[a[i]]++;

Answer 2

a0+a1+...+an-1=n
if a0=0
无解
得到所有的可能的数组
一个一个排除把