313. Super Ugly Number

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

class Solution { 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]; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。