腾讯面试题（统计数字出现的次数问题）

时间：2014.04.28

地点：基地二楼

日志：知道自己没有尝试着去试图改变，晓得错了~~

----------------------------------------------------------------

一。题目：

  给你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次....

以此类推..

----------------------------------------------------------------

二、解析：

  迭代法，就是不断地迭代和更新。先设置一个初始化数组，数据随意，随后不断的更新和调整数组，最后会收敛到一个稳定值，底部数组不再发生变化为止，但一直不收敛则表示无解。完成的源码实现如下：

#include<iostream>
using namespace std;
int GetDataCount(const int arr[], size_t size, int target);
//PRECONTION:
//POSTCONDITION:
//FACILITIES LIBRARY USED:

bool UpdateCountArray(int arr[], size_t size);
//PRECONTION:
//POSTCONDITION:
//FACILITIES LIBRARY USED:
void FinalCountArray(int arr[], size_t size);
//PRECONTION:
//POSTCONDITION:
//FACILITIES LIBRARY USED:
int main()
{
	int top_array[10];
	for (size_t i = 0; i < 10; ++i)
		top_array[i] = i;
	int bottom_array[10] = { 0 };
	FinalCountArray(bottom_array, 10);
	for (auto e : bottom_array)
		cout << e << '\t';
	return 0;
}

bool UpdateCountArray(int arr[], size_t size)
{
	bool change_occur = false;
	int frequency = 0;
	for (size_t i=0; i < size; ++i)
	{
		//bool change_occurr = false;
		frequency = GetDataCount(arr, size, i);
		if (frequency != arr[i])
		{
			arr[i] = frequency;
			change_occur = true;
		}
	}
	return change_occur;
}
int GetDataCount(const int arr[], size_t size, int target)
{
	int count = 0;
	for (size_t i = 0; i < size; ++i)
	{
		if (target == arr[i])
			++count;
	}
	return count;
}
void FinalCountArray(int arr[], size_t size)
{
	bool change = true;
	while (change)
		change = UpdateCountArray(arr, size);
}