腾讯面试题,给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数

腾讯面试题,给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数 - CSDN - 博客频道 - CSDN.NET
给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】
举一个例子，
数值: 【 0,1,2,3,4,5,6,7,8,9 】
分配: 【 6,2,1,0,0,0,1,0,0,0 】

http://blog.csdn.net/wcyoot/article/details/6428305

做以下分析：设总共有n个数，上排a[0...n-1],下排b[0...n-1]，。

1）下排n个数的累加和为n，即b[0]+b[1]+...+b[n-1] = n

2）ai*bi的累加和也为n，即a[0]*b[0]+a[1]*b[1]+...+a[n-1]*b[n-1] = n

3）对于b中任意一个元素b[j], 都存在i，a[i] = b[j].

4）对于b中任意一个元素b[j],都有b[j] >= 0

5）如果a中存在负数。其在b中出现的次数一定为0. 如果a中数值大于n，则其出现次数也为0.

6）a中至少有两个非0数值在b中出现的次数非0

http://blog.csdn.net/linraise/article/details/10554327
仔细观察,可以发现一个共同点:
对于一个数组A[n],下排的数字总和为n.
可以由之前的字符的全排列中找到灵感.
因此可以定义一个函数ArrayF(int* A,int n,int Sum),这个函数的功能是:使得A[0]+A[1]+A[2]+….+A[n-1]=Sum.其中A[i]=m,i=0,1,2,3….n-1,0<m<n-1.
这样子就可以用分治法来解决这个问题了.
假设A[n-1]取值i,则i的可能性是:0,1,2,3,4……n-1.则余下来的n-1个元素的数组就可以调用ArrayF(A,n-1,Sum-i)来解决.
递推式:
F(A[n],Sum)=:(A[0]=Sum) n==1
F(A[n],Sum)=:(A[n-1]=i)+F(A[n-1],Sum-i) n>1 ,i=0,1,2,3…..

由上面的递推式容易写出如下的递归函数.

void ArrayF(int* A,int n,int Sum)
{
 if(!A || n < 1 || Sum < 1)//处理异常,A==NULL,n <=0,Sum<1 
  return ;
 if( n==1 )
 {
  A[0]=Sum;
  for(int i=0;i<Len;++i)
   cout<<A[i]<<' ';
  cout<<endl;
 }
 else
 {
  for(int i=0;i<=Sum;++i)
  {
   A[n-1]=i;
   ArrayF(A,n-1,Sum-i);
  }
 }
}

由上面的函数求出所有的可能输出之后,再写一个函数判断输出序列是否满足条件即可.

时间复杂度为o(n^2),也可以用一个哈希表降低时间复杂度,但是,那样空间复杂度将会是o(n),时间复杂度是o(n).

bool isLegal(int* A,int n)
{
 for(int i=0;i<n;++i)
 {
  int count=0;
  for(int j=0;j<n;++j)
  {
   if(i==A[j])
    ++count;
  }
  if(A[i] != count)
   return false;
 }
 return true;
}

http://onestraw.net/algorithm/tencent-interview-problem-1/

使用穷举法, 得到10的10次方个排列，然后再判断每个排列是否满足条件，但是时间复杂度太高，其实9最多只能出现1次（9个0，1个9，这时也不满足条件，因为出现一个1），设置一个相对较小的上界函数

限界函数：a[i]最小为0，考虑a[i]的最大值
i个0，
i个1,
i个2,
… i个k,

有(k+1)*i<10

得到   a[i]< k < 10/i – 1
即 0=< a[i] < 10/i – 1
由于i可能为0，所以当不等式改写为
0=< a[i] <=10/(i+1)

i               0 1 2 3 4 5 6 7 8 9
a[i] max  10 5 3 2 2 1 1 1 1 1
其实际意义也正确

to-do:  http://www.cnblogs.com/tractorman/p/4053794.html
Read full article from 腾讯面试题,给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数 - CSDN - 博客频道 - CSDN.NET