面试题 49. 丑数
题目描述
题目:把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
设计一个算法,找出只含素因子2,3,5 的第 n 小的数。符合条件的数如:1, 2, 3, 4, 5, 6, 8, 9, 10, 12 ...
解答过程
样例
如果n = 9, 返回 10。
挑战
要求时间复杂度为O(nlogn)或者O(n)
Java 实现
public class Solution {
public int GetUglyNumber_Solution(int n) {
if(n<=0)
return 0;
if(n==1)
return 1;
int[] nums = new int[n];
nums[0] = 1;
int p2 = 0,p3 = 0,p5 = 0;
for(int i=1;i<n;i++){
nums[i] = Math.min(nums[p2]*2,Math.min(nums[p3]*3,nums[p5]*5));
if(nums[i]==nums[p2]*2) p2++;
if(nums[i]==nums[p3]*3) p3++;
if(nums[i]==nums[p5]*5) p5++;
}
return nums[n-1];
}
}
题目描述
题目:描述写一个程序来检测一个整数是不是丑数。
丑数的定义是,只包含质因子 2, 3, 5 的正整数。比如 6, 8 就是丑数,但是 14 不是丑数以为他包含了质因子 7。
可以认为 1 是一个特殊的丑数。
样例
给出 num = 8,返回 true。
给出 num = 14,返回 false。
Java 实现
public class Solution {
/**
* @param num: An integer
* @return: true if num is an ugly number or false
*/
public boolean isUgly(int num) {
// write your code here
boolean b = false;
if(num==1)
return true;
if(num<1)
return false;
while(num!=1){
if(num%2==0){
num=num/2;
}else if(num%3==0){
num=num/3;
}else if(num%5==0){
num=num/5;
}else{
return false;
}
}
return true;
}
}