LintCode第4题-丑数 II
描述
如果一个数只有质数因子2，3，5 ，那么这个数是一个丑数。
前10个丑数分别为 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...设计一个算法，找出第N个丑数。
我们可以认为 1 也是一个丑数
1≤n≤1690
样例 1：
输入：
n = 9输出：
10解释：
[1,2,3,4,5,6,8,9,10,....]，第9个丑数为10。
样例 2：
输入：
n = 1输出：
1思路:
先来看O(n²)的思路 后面为O(n)的思路
首先是O(n²)的思路
从 1 开始逐个生成丑数。
通过除以 2, 3, 5 来最终判断是不是丑数
条件为:
//除的时候要是 2 3 5
//返回的时候要 1 2 3 5才能算是丑数 由于已经把特殊的1包含进去了 所以只需要判断2 3 5即可
类似于LintCode第460题 先取一个数 然后在方法内在进行遍历判断
代码如下:
public class Solution {
/**
* @param n: An integer
* @return: return a integer as description.
*/
public int nthUglyNumber(int n) {
// write your code here
//除的时候要是 2 3 5
//返回的时候要 1 2 3 5才能算是丑数
List<Integer> uglyNumberList=new ArrayList<>();
//初始化
uglyNumberList.add(1);
int returnIndex=0;//1对应的返回值为0
int m=2;
while(uglyNumberList.size()<n)
{
boolean currentFlag=isCheckUglyNumber(m);
if(currentFlag)
{
uglyNumberList.add(m);
returnIndex++;
}
m++;
}
return uglyNumberList.get(n - 1);
}
boolean isCheckUglyNumber(int m)
{
boolean currentFlag=true;
while(m>1)
{
if(m%2==0)
{
m=m/2;
}else if(m%3==0)
{
m=m/3;
}
else if(m%5==0)
{
m=m/5;
}else
{
currentFlag=false;
return currentFlag;
}
}
return currentFlag;
}
}
思路2:下面是O(n)的思路 其中三指针法核心思路和动态规划很相似
即
三指针的三种状态：
dp[p2]：表示所有已生成丑数中，下一个乘以 2 的最小值。
dp[p3]：表示所有已生成丑数中，下一个乘以 3 的最小值。
dp[p5]：表示所有已生成丑数中，下一个乘以 5 的最小值
通过已知的丑数（ 数组）动态生成下一个最小丑数。
通过三个指针 p2, p3, p5 保持生成有序
public class Solution {
/**
* @param n: An integer
* @return: return the nth ugly number.
*/
public int nthUglyNumber(int n) {
if(n<=0)
{
return 0;
}
int uglyNumbers[]=new int[n];
uglyNumbers[0]=1;//第一个丑数是 1
int p2=0,p3=0,p5=0;// 三个指针
for(int i=1;i<n;i++)
{
int uglyNextValue=Math.min(uglyNumbers[p2]*2,Math.min(uglyNumbers[p3]*3,uglyNumbers[p5]*5));// 下一个丑数是三个指针对应数值的最小值
uglyNumbers[i]=uglyNextValue;
//更新指针：确保没有重复 注意这里的确保意思为确保每次生成的 “下一个丑数” 是 唯一且最小的
if(uglyNextValue==uglyNumbers[p2]*2)
{
p2++;
}
if(uglyNextValue==uglyNumbers[p3]*3)
{
p3++;
}
if(uglyNextValue==uglyNumbers[p5]*5)
{
p5++;
}
}
return uglyNumbers[n-1];
}
}