首页 > 代码库 > 剑指offer之寻找丑数,待字闺中之序列生成分析

剑指offer之寻找丑数,待字闺中之序列生成分析

题目来源:剑指offer之寻找丑数 与 待字闺中之序列生成分析

两个题目其实是同一个问题,所有放在一起,算是总结一下,题目如下:

给定一个表达式2^i*2^j,其中i,j为非负整数。请找到一种方法,生成如下序列:

2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25
...
...
...

阅读题目,要得到生成的数字序列是有序的,尽管题目中,并没有明说。这个题目的方法,是比较多的。我们在这里介绍几个。

一个简单的方法

很多同学,应该接触过丑数那个题目吧?这个题目相比之下,还要简单一些。i,j分别是2和5的指数, 则方法的过程如下:

i,j 从0开始,记录较小的值作为序列的当前生成值。则i=j=0时,最小值为1,就是第一个元素;

两个值都是最小元素,所以i和j,都自增1,在最小值1的基础之上乘以2和5得到2,5, 取较小的2作为序列的值,即2,第二个;

此时,只对i进行变化,自增1,在其上一个值的基础之上乘以2,即,2*2=4,再与5比较最小值。具体代码如下:

vector<int> UglyNumber(int n)
{
	vector<int> ugly(n);
	ugly[0] = 1;
	int i2 = 0,i5 = 0,index;//i2和i5表示当前即将乘以2和5的下标
	for(index = 1;index < n;index++)
	{
		int curUgly = min(ugly[i2]*2,ugly[i5]*5);
		ugly[index] = curUgly;
		while(ugly[i2] * 2 <= curUgly)i2++;  //修改i2
		while(ugly[i5] * 5 <= curUgly)i5++; //修改i5
	}
	return ugly;
}

int main()
{
	int n;
	while(cin >> n)
	{
		vector<int> ugly = UglyNumber(n);
		for(int i = 0;i < n;i++)cout << ugly[i] << " ";
		cout << endl;
	}
}