Super Ugly Number

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:

(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

Tips:

和ugly numberII类似，只是此时如果用set来存已经加过的数，此时因为prime的数量巨大，可能会超出内存。II的代码在最下方。

heap方法:要先定义一个新类Num(int index, int prime, int val),代表这个数理这个prime乘了几次之后又这个val，ugly[i]代表有这是第几个丑数。所以可以 while(heap.peek.val() == ugly[i]) 来判断当前最小丑数是不是把所有的prime都拿出来乘了放进heap里。

直接方法：这道题让我们求超级丑陋数，是之前那两道Ugly Number 丑陋数和Ugly Number II 丑陋数之二的延伸，质数集合可以任意给定，这就增加了难度。但是本质上和Ugly Number II 丑陋数之二没有什么区别，由于我们不知道质数的个数，我们可以用一个idx数组来保存当前的位置，然后我们从每个子链中取出一个数，找出其中最小值，然后更新idx数组对应位置，注意有可能最小值不止一个，要更新所有最小值的位置.

Code:

Heap: O(log(k)N)

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        PriorityQueue<Num> heap = new PriorityQueue<>();
        int[] ugly = new int[n];
        ugly[0] = 1;
        for (int i = 0; i < primes.length; i++) {
            heap.add(new Num(1, primes[i], primes[i]));
        }
        for (int i = 1; i < n; i++) {
            ugly[i] = heap.peek().val;
            while (heap.peek().val == ugly[i]) {
                Num cur = heap.remove();
                heap.add(new Num(cur.index + 1, cur.prime, ugly[cur.index] * cur.prime));
            }
        }
        return ugly[n - 1];
    }

    private class Num implements Comparable<Num>{
        int index;
        int prime;
        int val;

        public Num(int index, int prime, int val) {
            this.index = index;
            this.prime = prime;
            this.val = val;
        }

        public int compareTo(Num that) {
            return this.val - that.val;
        }
    }
}

直接：O(kN)

public class Solution {
    /**
     * @param n a positive integer
     * @param primes the given prime list
     * @return the nth super ugly number
     */
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] times = new int[primes.length];
        int[] uglys = new int[n];
        uglys[0] = 1;

        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; j++) {
                min = Math.min(min, primes[j] * uglys[times[j]]);
            }
            uglys[i] = min;

            for (int j = 0; j < times.length; j++) {
                if (uglys[times[j]] * primes[j] == min) {
                    times[j]++;
                }
            }
        }
        return uglys[n - 1];
    }
}

Upgly Number II:

// version 1: O(n) scan class Solution { /**

     * @param n an integer
     * @return the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        List<Integer> uglys = new ArrayList<Integer>();
        uglys.add(1);

        int p2 = 0, p3 = 0, p5 = 0;
        // p2, p3 & p5 share the same queue: uglys

        for (int i = 1; i < n; i++) {
            int lastNumber = uglys.get(i - 1);
            while (uglys.get(p2) * 2 <= lastNumber) p2++;
            while (uglys.get(p3) * 3 <= lastNumber) p3++;
            while (uglys.get(p5) * 5 <= lastNumber) p5++;

            uglys.add(Math.min(
                Math.min(uglys.get(p2) * 2, uglys.get(p3) * 3),
                uglys.get(p5) * 5
            ));
        }

        return uglys.get(n - 1);
    }
};

// version 2 O(nlogn) HashMap + Heap

class Solution {
    /**
     * @param n an integer
     * @return the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        // Write your code here
        Queue<Long> Q = new PriorityQueue<Long>();
        HashSet<Long> inQ = new HashSet<Long>();
        Long[] primes = new Long[3];
        primes[0] = Long.valueOf(2);
        primes[1] = Long.valueOf(3);
        primes[2] = Long.valueOf(5);
        for (int i = 0; i < 3; i++) {
            Q.add(primes[i]);
            inQ.add(primes[i]);
        }
        Long number = Long.valueOf(1);
        for (int i = 1; i < n; i++) {
            number = Q.poll();
            for (int j = 0; j < 3; j++) {
                if (!inQ.contains(primes[j] * number)) {
                    Q.add(number * primes[j]);
                    inQ.add(number * primes[j]);
                }
            }
        }
        return number.intValue();
    }
};