264. Ugly Number II

Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

Solution：

思路： 在ugly-sequence自己基础上再 * 2, 3, 5产生新的。用index/progres数组记录factor已经在自己原数组上乘到的位置(已经用过的)，三个对应位置取出最小的，更新位置。

屏幕快照 2017-09-09 下午7.33.24.png

Time Complexity: O(N) Space Complexity: O(N)

Solution1_a Code：

public class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
        for(int i=1;i<n;i++){
            int min = Math.min(Math.min(factor2,factor3),factor5);
            ugly[i] = min;
            if(factor2 == min)
                factor2 = 2*ugly[++index2];
            if(factor3 == min)
                factor3 = 3*ugly[++index3];
            if(factor5 == min)
                factor5 = 5*ugly[++index5];
        }
        return ugly[n-1];
    }
}

Solution1_b Code：

class Solution {
    public int nthUglyNumber(int n) {
        int factors[] = new int[] {2, 3, 5};
        int progres[] = new int[factors.length];  //for factors' own progress
        
        int result[] = new int[n + 1];
        result[0] = 1;
        
        for(int i = 1; i <= n; i++) {
            // get min value from factors.length of candidates
            int g_min = Integer.MAX_VALUE;
            for(int f = 0; f < factors.length; f++) {
                int cur_min = factors[f] * result[progres[f]];
                if(cur_min < g_min) g_min = cur_min;
            }
            // update those winning(include ties) candidates' progress
            for(int f = 0; f < factors.length; f++) {
                if(factors[f] * result[progres[f]] == g_min) progres[f]++;
            }
            result[i] = g_min;
        }
        
        return result[n - 1];
    }
}