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, is the sequence of the first 12 super ugly numbers given primes = 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 ≤ 10^6, 0 < primes* < 1000.
类似Ugly number二,创建长度为n的数组,依次生成n个ugly number。代码如下:
public class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int[] count = new int[primes.length];
int[] result = new int[n];
result[0] = 1;
int index = 1;
while(index < n) {
int min = Integer.MAX_VALUE;
for(int i = 0; i < count.length; i++) {
if(min > result[count[i]] * primes[i])
min = result[count[i]] * primes[i];
}
result[index ++] = min;
for(int i = 0; i < count.length; i++) {
if(min == result[count[i]] * primes[i]) count[i] ++;
}
}
return result[n - 1];
}
}