264. Ugly Number II

题目描述和难度

  • 题目描述：

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

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

示例:

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

说明:  

  1. 1 是丑数。
  2. n 不超过1690。

思路分析

求解关键：这道题的解法可以参考何海涛编著的《剑指Offer》第 49 题：丑数（P240）的分析。

参考解答

参考解答1

public class Solution {

    public int nthUglyNumber(int n) {
        if (n < 7) {
            return n;
        }
        int[] dp = new int[n];
        int index2 = 0;
        int index3 = 0;
        int index5 = 0;
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = min3(dp[index2] * 2, dp[index3] * 3, dp[index5] * 5);
            if (dp[i] == dp[index2] * 2) {
                index2++;
            }
            if (dp[i] == dp[index3] * 3) {
                index3++;
            }
            if (dp[i] == dp[index5] * 5) {
                index5++;
            }
        }
        return dp[n - 1];
    }

    private int min3(int num1, int num2, int num3) {
        return Integer.min(Integer.min(num1, num2), num3);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int nthUglyNumber = solution.nthUglyNumber(30);
        System.out.println(nthUglyNumber);
    }
}

参考解答2：根据 LeetCode 第 313 题“超级丑数”的思路，其实这道题就是“超级丑数”的特例。

public class Solution3 {

    public int nthUglyNumber(int n) {
        int[] primes = new int[3];
        primes[0] = 2;
        primes[1] = 3;
        primes[2] = 5;
        int[] indexes = new int[3];
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < 3; j++) {
                dp[i] = Integer.min(dp[i], dp[indexes[j]] * primes[j]);
            }
            for (int j = 0; j < 3; j++) {
                if (dp[i] == dp[indexes[j]] * primes[j]) {
                    indexes[j]++;
                }
            }
        }
        return dp[n - 1];
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0264-ugly-number-ii ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。