题目描述:
我们把只包含因子2,3,5的数称作丑数(Ugly Number)。
求从小到大顺序的第1500个丑数。
例如:6,8是丑数,而14不是,因为它还包含因子7。
习惯上,我们把1作为第一个丑数。
思路:
1)从1到n遍历一遍,每次判断是否丑数。时间消耗较大。
2)空间换时间,定义一个数组存放n个丑数。
具体代码如下:
1)
bool IsUgly(int number) { while(number % 2 == 0) number /= 2; while(number % 3 == 0) number /= 3; while(number % 5 == 0) number /= 5; return (number == 1) ? true : false; } int GetUglyNumber_Solution1(int index) { if(index <= 0) return 0; int number = 0; int uglyFound = 0; while(uglyFound < index) { ++number; if(IsUgly(number)) { ++uglyFound; } } return number; }
2)数组中的每一个数取*2、*3、*5中最小的那个,并相应的后移指针。
int Min(int number1, int number2, int number3); int GetUglyNumber_Solution2(int index) { if(index <= 0) return 0; int *pUglyNumbers = new int[index]; pUglyNumbers[0] = 1; int nextUglyIndex = 1; int *pMultiply2 = pUglyNumbers; int *pMultiply3 = pUglyNumbers; int *pMultiply5 = pUglyNumbers; while(nextUglyIndex < index) { int min = Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5); pUglyNumbers[nextUglyIndex] = min; while(*pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex]) ++pMultiply2; while(*pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex]) ++pMultiply3; while(*pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex]) ++pMultiply5; ++nextUglyIndex; } int ugly = pUglyNumbers[nextUglyIndex - 1]; delete[] pUglyNumbers; return ugly; } int Min(int number1, int number2, int number3) { int min = (number1 < number2) ? number1 : number2; min = (min < number3) ? min : number3; return min; }