leetcode 313 Super Ugly Number
z
 2018-05-27 19:32:42  

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.
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int size = primes.length;
        int[] nums = new int[size];
        
        for(int i=0; i<size; i++){
            nums[i] = primes[i];
        }
        
        int[] index = new int[size];
        int[] ans = new int[n];
        ans[0] = 1;
        
        for(int i=1; i<n; i++){
            int min = Integer.MAX_VALUE;
            
            for(int j=0; j<size; j++){
                min = Math.min(min, nums[j]);
            }
            ans[i] = min;
            for(int j=0; j<size; j++){
                if(ans[i] == nums[j]){
                    index[j] ++;
                    nums[j] = ans[index[j]] * primes[j];
                }
            }
            
        }
        return ans[n-1];
        
    }
}