微软等数据结构与算法面试100题 第六题
第六题
题目：
给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】
分析：这道题拿到题目第一感觉是使用迭代算法计算，终止条件是求解得到上面的解。
如果使用迭代算法，会造成一下两个问题：1，迭代算法不能够保证收敛，因此可能陷入死循环，或者说是收敛不到解。2，迭代算法不能够求解全部的解，只能得到满足该
条件的一个解。
使用迭代算法的代码如下：
[cpp]
#include<iostream>
#include<stdio.h>
using namespace std;
bool timeNoOf(int * timeNoOf, int * Array, const int length)
{
bool success = true;
for(int i = 0; i < length; i++) timeNoOf[i] = 0;
for(int i = 0; i < length; i++)
{
timeNoOf[Array[i]] = timeNoOf[Array[i]] + 1;
}
for(int i = 0; i < length; i++)
{
if(timeNoOf[i]!=Array[i])
{
success = false;
Array[i] = timeNoOf[i];
}
}
//int sum=0;
//for(int i=0; i<length-1; i++) sum = sum + Array[i];
//Array[length-1] = length - sum;
return success;
}
void timesNoArray(int *a, int * timeNo, const int length)
{
for(int i=0; i < length; i++) timeNo[i] = 0;
bool success = false;
while(!success){
//update the timeNo array
success = timeNoOf(timeNo, a, length);
for(int i =0; i < 10; i++ ) cout<< timeNo[i]<<" ";
cout<<endl;
}
}
int main()
{
int a[] = {0,1,2,3,4,5,6,7,8,9};
int b[] = {0,1,2,3,4,5,6,7,8,9};
timesNoArray(a,b,10);
for(int i =0; i < 10; i++ ) cout<< b[i]<<" ";
return 0;
}
在测试例子的时候，发现当n=10，即十个数如 0 1 2 3 4 5 6 7 8 9时候会在两个解之间摆动，但是收敛不到需要求解的解。
其它更好的求解算法待后续补充！也请各位大牛指正！
补充：软件开发 , C++ ,
