剑指offer 丑数
- 题目描述
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
- 题目解答
这道题目有两种解法：
-
暴力求解 —— 对于每个数都去判断是否是丑数，直到找到第N个丑数返回。
-
用一个数组来保存一个有序的丑数数组，每一个丑数都是前面的丑数乘以2、3、5得到的。
class Solution {
public:
int GetUglyNumber_Solution(int index) {
if (index <= 0)
return 0;
int *ugly = new int[index];
ugly[0] = 1;
int nextIndex = 1;
int *index_2 = ugly;
int *index_3 = ugly;
int *index_5 = ugly;
while (nextIndex < index){
ugly[nextIndex] = getMin(*index_2 * 2, *index_3 * 3, *index_5 * 5);
while (*index_2 * 2 <= ugly[nextIndex])
++index_2;
while (*index_3 * 3 <= ugly[nextIndex])
++index_3;
while (*index_5 * 5 <= ugly[nextIndex])
++index_5;
++nextIndex;
}
int ret = ugly[index - 1];
delete[] ugly;
return ret;
}
int getMin(int x, int y, int z){
int t = x > y ? y : x;
return z > t ? t : z;
}
};