首页 > 代码库 > 剑指offer 66题 -- 丑数
剑指offer 66题 -- 丑数
class Solution {
public:
int GetUglyNumber_Solution(int index) {
//变量定义区
int subA=0, subB=0, subC=0;
int sub =0;
int* array = new int[index];
array[0] = 1;
if(index <= 0)
return 0;
//分析:数组的后面的每一个元素必定是由数组前面的某一个乘以2,3,或者5得到
// 也就是说, 每个当前的值,都是由前面的某个值的2倍,3倍,5倍 贡献的。
// 至于具体由哪个贡献,需要选择最小的值。
// 这样,可以维护四个下标变量,一个记录数组当前下标值,另外三个分别记录2,3,5的下标值
//每次选取当前值中的2,3,5的倍数中的最小值, 然后需要判断这三个值 是不是大于 当前值,
//如果不大于,那么需要更新这三个值得下标,也就是向前移位,直到大于当前值。
while(sub < index-1)
{
//当2的倍数低于(等于)当前值,需要前移
while( array[subA]*2 <= array[sub])
++subA;
//
while( array[subB]*3 <= array[sub])
++subB;
while( array[subC]*5 <= array[sub])
++subC;
//需要取最小的值作为当前值
array[++sub] = min( array[subA]*2, array[subB]*3, array[subC]*5);
}
int result = array[index-1];
delete [] array;
return result;
}
int min(int n1,int n2,int n3)
{
int minimum=0;
minimum = (n1 < n2) ? n1:n2;
minimum = (minimum < n3) ? minimum:n3;
return minimum;
}
};
剑指offer 66题 -- 丑数