Question

Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Thinking:

  • Method 1:
    • Ugly number的定义是分解质因数都是2,3,5.
    • 我们设计一个数组用于存储丑数，初始化为1.
    • 将每个位置的数字x2, x3, x5，取出最小值。
    • 维护三个index，表示当前对于哪个数字进行乘法运算。
class Solution {
    public boolean isUgly(int num) {
        if(num == 1) return true;
        if(num <= 0) return false;
        if(num == 2 || num == 5 || num == 3) return true;
        if(num % 2 == 0) return isUgly(num / 2);
        if(num % 3 == 0) return isUgly(num / 3);	//使用if可以去重。
        if(num % 5 == 0) return isUgly(num / 5);
        return false;
    }
}

Second time

  1. This question can be solved by dp
  2. except for 1, all the other values in dp array should be 2,3 or 5 multipling a previous value in the array.
  3. We hold three indices for 2, 3 and 5 so we can know what is the “current” value this value is multipling to.
  4. For each index in dp array, we have a change to select which numbers(may duplicate) by comparing the value, and easy to understand, dp[i] save the minimum number hold by (2, 3, 5). 
    class Solution {
 public int nthUglyNumber(int n) {
     int[] dp = new int[n + 1];
     dp[0] = 1;
     int index2 = 0, index3 = 0, index5 = 0;
     int factor2 = 2, factor3 = 3, factor5 = 5;
     for(int i = 1; i <= n; i++){
         dp[i] = Math.min(factor2, Math.min(factor3, factor5));
         if(dp[i] == factor2) factor2 = dp[++index2] * 2;
         if(dp[i] == factor3) factor3 = dp[++index3] * 3;
         if(dp[i] == factor5) factor5 = dp[++index5] * 5;
     }
     return dp[n - 1];
 }
}