uppernum.cpp

给定一个数组A

// UpperNum.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include <vector>
#include <iostream>

using namespace std;
//给定一个数组A，里面只出现0-9这10个数字，但不一定全部出现，然后给定一个K的值，
//求A中大于K的整数当中最小的一个，并输出。例如A={0，1}， k =12,则结果为100.
// 数组UpperNumber表示不小于每个数字的最小数字，没有数字则选择最小的数字（按最小的两位数处理）
// 取K的每一个数字，逆序，选择不小于该数字的值，如果相等，则处理下一个数字，
// 如果大于，后面的数字取Upper[0], 如果小于，则前一位要进位

void UpperNumber(int A[], int length, int k)
{
	// setting Upper
	int Upper[11];
	Upper[0]=-1;
	int i;
	for (i = 0; i < length; i++) {
		Upper[A[i]] = A[i];
	}

	int up=Upper[0]>=0? Upper[0]:0;
	for (i = 9; i >=0; i--)
	{
		if (Upper[i] != i)
		{
			Upper[i] = up;
		}
		else
		{
			up = Upper[i];
		}
	}
	Upper[10] = Upper[0];

	//for (i = 0; i < 10; i++ )
	//{
	//	cout<<Upper[i];
	//}
	//cout<<endl;

	// get number of k
	vector<int> vKNum;
	while (k > 0)
	{
		int num = k%10;
		vKNum.push_back(num);
		k /= 10;
	}
	int count = vKNum.size();
	//for (i = count-1; i >=0; i--)
	//{
	//	cout<<vKNum[i];
	//}
	//cout<<endl;

	//int[]  upNum =new int[count+1];
	vector<int> vUpNum;
	vUpNum.assign(count+1, 0);

	// get upper number
	// big = true 则选择大于该数字的值，即Upper[x+1]，否则选不小于的Upper[x]，
	// 如果小于，则前一位要big；对于最高big位，低位全部设为Upper[0]
	bool big = true;
	int bigPos = 0;
	for (i=0; i<count; i++)
	{
		int ki = vKNum[i];
		if (big)
		{
			vUpNum[i] =Upper[ki+1];
		}
		else
			vUpNum[i] = Upper[ki];
		if (vUpNum[i] > ki)
		{
			big = false;
			bigPos = i;
		}
		else if (vUpNum[i] < ki)
		{
			big = true;
		}
	}
	//cout<<bigPos<<endl;

	// 检查最高位是否big
	if (big)
	{
		vUpNum[count] = Upper[1];
		bigPos = count;
	}
	for(i=bigPos-1;i>=0;i--)
	{
		vUpNum[i] = Upper[0];
	}
	int upK = 0;
	for (i=count; i>=0; i--)
	{
		upK = upK*10 + vUpNum[i];
	}
	cout<<upK;
}


int _tmain(int argc, _TCHAR* argv[])
{
	int A[] = { 7, 4,2, 0};
	int length = sizeof(A)/sizeof(int);
	int k = 74223598;

	UpperNumber(A, length, k);
	return 0;
}