本文共 2335 字，大约阅读时间需要 7 分钟。

题目原文：

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. 题目大意： 写一个程序计算第n个超级丑数。 超级丑数如下定义：超级丑数是一种正数，它的所有质因子都在给出的序列中。 例如：给定质数序列2,7,13,19，则1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32都是在这个质数序列下的丑数。 注意： （1）1是任意质数序列下的丑数； （2）质数序列是递增顺序的； 给出质数序列，求该序列下的第k个超级丑数。 题目分析： 观察例子中的丑数序列： 1 2 4=2*2 7 8=4*2 13 14=7*2 16=8*2 19 26=13*2 28=14*2 32=16*2 可以发现每个丑数都可以看做是素数序列中的一个数与较小的丑数的乘积。 那么可以使用两个辅助数组index和vals，其中index记录当前每个素数应该与已有解中的哪个数相乘，vals记录候选解，每次从vals中筛选出最小解，并令对应下标的index加1.最后用数组q存储每轮迭代的最优解。这样直接描述可能有些难以理解，以下给出迭代过程。 算法迭代过程如下：（设质数序列primes = {2,7,13,19}） 初始化： q={1} // 因为1永远是超级丑数 vals={0,0,0,0} index={0,0,0,0} // 所有素数都和q中第0个元素相乘 第一轮筛选： vals = {2,7,13,19} 选择2为最优解，加入数组q中，并更新index index = {1,0,0,0} //素数2与q中第1个元素相乘，其他都与第0个元素相乘 q={1,2} 第二轮筛选： vals = {4,7,13,19} 选择4为最优解，加入数组q中，并更新index： index = {2,0,0,0} //素数2与q中第2个元素相乘，其他都与第0个元素相乘 q={1,2,4} 第三轮筛选： vals = {8,7,13,19} 选择7为最优解，加入数组q中，并更新index： index = {2,1,0,0} //素数2与q中第2个元素相乘，7与第1个元素相乘，其他都与第0个元素相乘 q={1,2,4,7} 第四轮筛选： vals = {8,14,13,19} 选择8为最优解，加入数组q中，并更新index： index = {3,1,0,0} //素数2与q中第2个元素相乘，7与第1个元素相乘，其他都与第0个元素相乘 q={1,2,4,7} …… 一直到第k轮，返回q中最后一个元素即可。 源码：（language：java）

public class Solution {    public int nthSuperUglyNumber(int n, int[] primes) {        int size = primes.length;        int q[] = new int[n];        int idxes[] = new int[size];        int vals[] = new int[size];        q[0] = 1;        for (int i = 1; i < n; i++) {            for (int j = 0; j < size; j++) {                vals[j] = q[idxes[j]] * primes[j];            }            q[i] = findMin(vals);            for (int j = 0; j < size; j++) {                if (vals[j] == q[i]) {                    idxes[j] += 1;                }            }        }        return q[n - 1];    }    public int findMin(int[] nums) {        int min = nums[0];        for (int i = 1; i < nums.length; i++) {            min = Math.min(min, nums[i]);        }        return min;    }}

成绩：

39ms,beats 38.05%,众数32ms,6.33%

转载地址：http://xfomb.baihongyu.com/