264. Ugly Number II

三刷 06/2022

Version #1 DP

Time O(N)

Space O(N)

Runtime: 3 ms, faster than 87.56% of Java online submissions for Ugly Number II.

Memory Usage: 42.5 MB, less than 40.34% of Java online submissions for Ugly Number II.

class Solution {

    public int nthUglyNumber(int n) {

        // When we have only 1, we know the next number is between:

        //      1  2  3

        // * 2     x

        // * 3     x

        // * 5  x

        int p2 = 0, p3 = 0, p5 = 0;

        int[] nums = new int[n];

        nums[0] = 1;

        for (int i = 1; i < n; i++) {

            int n2 = nums[p2] * 2;

            int n3 = nums[p3] * 3;

            int n5 = nums[p5] * 5;

            int min = Math.min(n2, Math.min(n3, n5));

            if (min == n2) {

                p2++;

            }

            if (min == n3) {

                p3++;

            } 

            if (min == n5) {

                p5++;

            }

            nums[i] = min;

        }

        return nums[n - 1];

    }

}

Version #2 Priority Queue

Time O(NlogN) -> Every time we poll a number, we added 3 numbers with O(log3N) time, total O(3Nlog3N) ~ O(NlogN)

Space O(N)

Runtime: 137 ms, faster than 9.87% of Java online submissions for Ugly Number II.

Memory Usage: 60.9 MB, less than 12.59% of Java online submissions for Ugly Number II.

class Solution {

    public int nthUglyNumber(int n) {

        if (n <= 5) {

            return n;

        }

        int[] factor = new int[]{2, 3, 5};

        Queue<Long> pq = new PriorityQueue<>();

        Set<Long> visited = new HashSet<>();

        pq.offer(Long.valueOf(1));

        Long num = null;

        while (n-- > 0) {

            num = pq.poll();

            for (int f : factor) {

                Long next = f * num;

                if (visited.contains(next)) {

                    continue;

                }

                visited.add(next);

                pq.offer(next);

            }

        }

        return num.intValue();

    }

}

二刷

最tricky的点在于 有可能有多个next值同时等于min
这个时候所有等于min的pointer都要++
class Solution {
    public int nthUglyNumber(int n) {
        //    i    1  2  3  4  5  6  7  8  9   10
        // index
        // dp[i] = 1, 2, 3, 4, 5, 6, 8, 9, 10, 12
        // dp2[] = 2*1, 2*2, 2*3,...
        // dp3[] = 3*1, 3*2, 3*3,...
        // dp5[] = 5*1, 5*2, 5*3,...
        int index2 = 1, index3 = 1, index5 = 1;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int next2 = 2 * dp[index2];
            int next3 = 3 * dp[index3];
            int next5 = 5 * dp[index5];
            int min = Math.min(next2, Math.min(next3, next5));
            if (min == next2) {
                index2++;
            }
            if (min == next3) {
                index3++;
            }
            if (min == next5) {
                index5++;
            }
            dp[i] = min;
        }
        return dp[n];
    }
}

一刷
做了超久。。。。
算法没看懂就着急写了
主要就是dp的思想

50.83%

public class Solution {
    public int nthUglyNumber(int n) {
        if (n <= 0) return n;
        int[] ugly = new int[n];
        //Arbitrarily
        ugly[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        int m2, m3, m5, min;
        int index = 1;
        while (index < n) {
            m2 = ugly[p2] * 2;
            m3 = ugly[p3] * 3;
            m5 = ugly[p5] * 5;
            min = Math.min(m2, Math.min(m3, m5));
            //System.out.println(min);
            ugly[index++] = min;
            if (min == m2) p2++;
            if (min == m3) p3++;
            if (min == m5) p5++;
        }
        return ugly[index - 1];
    }
}