参考http://blog.csdn.net/heaven13483/article/details/7925621
腾讯面试题:
给你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
0 在下排出现了6 次,1 在下排出现了2 次,2 在下排出现了1 次,3 在下排出现了0 次....
以此类推..
数学方法:关键是理解“要求下排每个数都是先前上排那十个数在下排出现的次数”。
做以下分析:设总共有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.
(为了后续讨论的严谨,此处说明一下:对于不在0~n内的数可以将其替换为a数列中0~n中所缺失的数,由于出现0次,所以不影响累加和以及卷积和,后面将说明a数列中0、1、2和n-4必不可少,这里假设四个数互不相同,且在0~n内,有n-4>2,即n>=7,最后将看到n<=6的几种特殊情况)
6)a中至少有两个非0数值在b中出现的次数非0
a:由1)n > n*b[i],其中b[i]为最小值,则a b中一定均有数值0,否则无解。设a[0] = 0,b[0]为a[0]在b中出现次数。
b:由于b中一定存在0,则0的出现次数一定大于0,因此b[0]>0 且b[0] < n,b[1...n-1]中至少一个值为0. 非0元素出现的次数一共是n-b[0].
c:有2)和6)对任意a[i],a[i]*b[i] < n(=不成立,如果只有1个数,若a[i]不等于b[i],则多于1个数;若a[i]等于b[i]且收敛,除非a数列只有1这个数),即b[i]
< n/a[i],对所有a[i]>=n/2的元素中,在b中出现的次数必须最多只有1个出现次数不为0,且为1.其余出现次数均为0,又[0, n/2)范围内最多只有n/2-1个元素,即最多只有n/2个元素不为0,故0出现的次数必不小于n/2, [n/2,n)范围内的元素必有一个出现次数为1,设为y,即b[y]=1。因此a数列中也必须有1,否则无解。
d:1出现的次数至少为1(由c得)。又如果1出现的次数为1,则1出现的次数已经为2,故1出现的次数必大于1.设为x(2<=x<n/2,否则与c矛盾),则x出现的次数至少为1,而x>1,如果x出现的次数大于1,那么必须要有其他数出现的次数为x,这样无法收敛。故x出现的次数只能为1,由后续证明知2~n中最多有两个位置非0,此处b[x]=b[y]=1,其他位置必须全0。这样可知1出现的次数只能为2,那么x只能等于2
结论:
0出现的次数为n-4(0、1、2、n-4出现的次数非0),1出现的次数为2,2出现的次数为1。n-4出现的次数为1.如果数列中无这四个数,无解。
证明2~n至多有两个数出现1次或者一个数出现2次,即至多有两个安排位置,可以放在b[0]和b[1];如果放在其他位置>=2,最终会导致安排位置无止境的增多以致无法安排
1) 如果有至少三个数出现1次及以上,不妨设这三个数为p、q、r,满足p,q,r>=2且互不相等.当p、q、r均出现1次时,可以让b[0]和b[1]等于其中的两个数,然后b[i]等于另一个数,不妨设b[0]=p,b[1]=q, b[i]=r,2<=i<=n/r(ai*bi的累加和也为n),这样i出现了r次。
即便i等于p、q、r中的一个(也相当于后续讨论的p、q、r至少有一个元素出现1次以上这种情况)且r=2,即至少还有一个i需要找到位置,不妨设b[j]=i。
若j不等于p、q、r,且j>=2,那么j是一个新的元素,至少出现了两次,那么新安排的位置也必然位于2~n,最后导致所有的位置至少都出现一次,无法自我满足条件。
如果j等于p、q、r中的一个,那么相当于p、q、r至少有一个元素出现1次以上,可以先安排p、q、r均出现1次的情况,然后处理剩余的出现次数,这样比上述情况更难安排,最终也会导致所有的位置至少都出现一次,无法自我满足条件。
当多于三个数出现出现1次及以上时,可以先安排其中三个数的情况,然后处理剩余的出现次数,这样比上述情况更难安排,最终也会导致所有的位置至少都出现一次,无法自我满足条件。
其实无论新位置和老位置是否重合,出现次数是不停增多的,最终会导致位置用尽,无法安排以致自我矛盾
2)如果有两个数出现,且两个数中至少有一个数出现2次及以上,不妨设这两个数为p、q,p出现两次。可以当做p、p、q三个数各出现1次,根据上述论述,最终也会无法安排位置
3) 有一个数出现3次及以上,不妨设为p,出现3次。可以当做p、p、p三个数各出现1次,根据上述论述,最终也会无法安排位置
两种特殊情况,n<=6
1
1
0 1 2 x(除0、1、2外的任意数)
2 0 2 0
n=2、3、5、6的时候未找到解
常规解法:它的原型跟八皇后有点类似,都是用回溯递归的方法去一次一次尝试,直到找出正确解。
具体的想法是:不断的去从下排数组中捉取在上排数组中对应位置中出现的个数,如果个数不对就更新下排数组中对应的值,只到找到正确值。(下排数组先初始为任意值)
如:
上排数组A:0,1,2,3,4,5,6,7,8,9
下排数组B:0,1,2,3,4,5,6,7,8,9
从上牌数组Index = 0开始,A[0] = 0,0在下排数组中的个数为1,那么下排数组B此时就要更新为:1,1,2,3,4,5,6,7,8,9,
Index = 1, A[1] =1, 1在下排数组中的个数为2,那么下排数组B此时就要更新为:1,2,2,3,4,5,6,7,8,9,从此不断的往下进行,只要找不到正确值就一直往下进行,如果Index >= 数组长度时,那么重新恢复Index = 0再往下进行测试直到找出正确解。
但这好象只能解决如上所述的情况,,即连续的N个数。
//不停重试以获得正确值 int* GetArray() { int i = 0; while(!success) { i++; SetNextArray(); } return Array; } //一次尝试中更新所有出现次数 void SetNextArray() { bool bRet = true; for(int i = 0; i < MAX_LEN; i++) { int nFreq = GetFrequecy(i); if(Array[i] != nFreq) { Array[i] = nFreq; bRet = false; } } success = bRet; } //遍历获取某个数nValue的出现次数 int GetFrequecy(int nValue) //此处的nValue 即指上排的数i { int nCnt = 0; for(int i = 0; i < MAX_LEN; i++) { if(m_aryBottom[i] == nValue) nCnt++; } return nCnt; //nCnt 即对应nFreq }