264. Ugly Number II

https://www.jiuzhang.com/problem/ugly-number-ii/

Solution 1

use minHeap

從小到大從 minheap 取數字出來

注意, heap 如果不用 long, 數字太大時是會錯的, 會超出int 範圍, 可能結果還會失去 sign 的符號變負的

time: O(3nlog3n)

space: O(3n)

class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        minHeap.offer(1L);
        Set<Long> set = new HashSet<>();
        set.add(1L);
        
        int primeFactor[] = new int[]{2,3,5};
        
        Long currUglyNum = 1L;
        for (int i = 0; i < n ; i++) { // 0~9, 9 is 10th
            currUglyNum = minHeap.poll();
            for (int factor : primeFactor) {
                Long newUglyNum = currUglyNum*factor;
                if (!set.contains(newUglyNum)) {
                    set.add(newUglyNum);
                    minHeap.offer(newUglyNum);
                }
            }
        }
        return currUglyNum.intValue();
    }
}

or like this, 10th = 0~(10-1-1) 0~8, at lasyt return index 9

    for (int i = 0; i < n-1; i++) { 
        long cur = heap.poll();
        for (int f : factor) {
            long newCur = cur*f;
            if (!set.contains(newCur)) {
                set.add(newCur);
                heap.offer(newCur);
            }
        }
    }
    return heap.poll().intValue();

min heap

time: O(3nlog3n)

space: O(3n)

class Solution {
    public int nthUglyNumber(int n) {
        Queue<Long> pq = new PriorityQueue<>();
        pq.offer(1l);

        int count = 0;
        while (!pq.isEmpty()) {
            long cur = pq.poll();
            while (!pq.isEmpty() && pq.peek() == cur) { // 塞入的數可能會有一樣的 ex: 6, 6
                pq.poll(); // 所以一樣的都要排掉
            }
            count++;
            if (count == n) {
                return (int)cur;
            }
            pq.offer(cur*2);
            pq.offer(cur*3);
            pq.offer(cur*5);
        }
        return -1;
    }
}

類似 DP

Ｔ: O(3N) = O(N)

S: O(N)

```java
class Solution {
    public int nthUglyNumber(int n) {
        int i = 0;
        int j = 0;
        int k = 0;

        List<Integer> result = new ArrayList<>();
        result.add(1);
        for (int t = 0; t < n-1; t++) { // n-1 次, 因為已經有一個1加入了
            // 這樣的做法就像是取代了pq, 每次只拿最小的出來(但3個候選人而已, 所以 T: O(3N), 變成線性的解法了)
            int cur = Math.min(Math.min(result.get(i)*2, result.get(j)*3), result.get(k)*5);
            result.add(cur);
            // 跟之前一樣, 一樣的要跳過, 所以 index++, result目的除了結果, 還會存 old ugly number , 之後就可以*2. *3. *5 去得到新的 ugly number
            if (result.get(i)*2 == cur) {
                i++;
            }
            if (result.get(j)*3 == cur) {
                j++;
            }
            if (result.get(k)*5 == cur) {
                k++;
            }
        }
        return result.get(result.size()-1);
    }
}
```

better explain:

class Solution {
    public int nthUglyNumber(int n) {
        List<Integer> result = new ArrayList<>();
        result.add(1);
        int i = 0, j = 0, k = 0;
        for (int t = 0; t < n-1;t++) { // 0
            int cur = Math.min(Math.min(result.get(i)*2, result.get(j)*3), result.get(k)*5);
            result.add(cur);
            if (result.get(i)*2 == cur) { // duplicated
                i++; // 1 -> become result.get(1) this is what we just add in res [1,2]
                // next round use 2, 2*2, 2*3, 2*5] add to min(2*2, 3, 5), get min is 3, result = [1,2,3]
                // next round use  min(2*2, 2*3, 5), get min is 4, result = [1,2,3, 4]
                // i -> 1 to 2
                // next round use  min(3*2, 2*3, 5), get min is 5, result = [1,2,3, 4, 5]
                // k -> 0 to 1
                // next round use  min(3*2, 2*3, 2*5), get min is 6, result = [1,2,3, 4, 5, 6]
                // i -> 2 to 3, j -> 1 to 2
                // next round use  min(4*2, 3*3, 2*5), get min is 8, result = [1,2,3, 4, 5, 6, 8]
                // ... anyway this means prime is unchange, but we move the result_idx to generate non-duplicated number
            }
            if (result.get(j)*3 == cur) {
                j++; // 0 -> 1
            }
            if (result.get(k)*5 == cur) {
                k++; // 0 -> 1
            }
        }
        return result.get(result.size()-1);
    }
}

```java
/**
T: O(3n)
S: O(n)

[2,3,5]
  1
       2        3          5
4 6 10       6   9  15    10,15,25

8 12 20  12 18 30 ...

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]

have to skip these duplicated number
pointers to record where is these duplicated number we have use

*5   k                  
*3   j                 
*2   i               
res  1

process:

*5     k                  
*3       j                 
*2         i               
res  1 2 3 4 5 6 ...
res = [1]
start from res = 1 to multiply
 */
```