264. 丑数 II/面试题49. 丑数(简单)

编写一个程序，找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:

1 是丑数。
n 不超过1690。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ugly-number-ii

思路：

剑指offer思路：每一个丑数，都是前面某个丑数2，3或5得来的

我们用一个数组接收所有的丑数，设当前最大丑数为M，先考虑前面某个丑数*2，会得到若干小于等于M的数，这些数都不需要，还有若干大于M的数，我们需要第一个，同理 * 3 *5一样，求得了三个大于M的数，下一个丑数就是在三个丑数中取最小的，就是下一个丑数了

dp[i] 表示第i个丑数

那么dp[i] = min(2 * dp[l_2], 3 * dp[l_3], 5 * dp[l_5])

这里 l_2, l_3, l_5是表示，指到的位置。

时间复杂度：O(n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int nthUglyNumber(int n) {
        //dp，三指针
        int[] dp = new int[n];
        dp[0]=1;
        int u2=0,u3=0,u5=0;
        for(int i=1;i<n;i++){
            int min = Math.min(dp[u2]*2,Math.min(dp[u3]*3,dp[u5]*5));
            if(min==dp[u2]*2)
                u2++;
            if(min==dp[u3]*3)
                u3++;
            if(min==dp[u5]*5)
                u5++;
            dp[i]=min;
        }
        return dp[n-1];
    }
}