题解Super Ugly Number

---

欢迎访问我的博客：http://www.fupinyou.com

问题描述：

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.

注意事项：

1 is a super ugly number for any given primes.The given numbers in primes are in ascending order.0 < k ≤ 100, 0 < n ≤ 10^6, 0 < primes[i] < 1000.

分析

题目大意就是说，超级丑陋数字就是由给定的素数因子组成的数字，给出n，要求返回第n个丑陋数字。而且素数因子是有序递增排列的。我心想，这么简单！直接一个for循环一次把素数因子数组从低到高乘起来不就可以了吗？仔细分析下来发现并没有这么简单。例如，丑陋数字数组的第三个数字是4，即1X2X2，而不是1X2X7！说明有的数字乘两次了都还比另外的数字乘一次要小！所以说前面的那种想法是错误的。再思考，每次都乘2会不会就是最小？这个不用想，肯定是错的，因为比如说第四个数字如果是1X7就比1X2X2X2要小。我们设丑陋数字数组为superuglynumbers[n]。1X7就是superuglynumbers[0]X7，而122*2就是superuglynumbers[2]X2，为什么它是后者用的是superuglynumbers[2]而前者是superuglynumbers[0]呢？
这里很显然就会想到次数的问题，因为我的数字2在之前用过两次，所以它会“认为”当前最小的数字就是丑陋数字数组的前一项superuglynumbers[2]乘以素数数组里面最小的数字2。而不是superuglynumbers[1]X2，因为这个组合它之前用过了，不能再用了，再用的话丑陋数字就重复出现了。但是并不一定它就是最小。
你应该看出来了，它用了4个数字相乘，而1X7只用了两个数字相乘。画个图你就明白了：

image
从图中你可以看出每个数字都是乘在它上一次的“高度”上。

解

我们可以用一个数组times[]来记录每个素数的用到的次数，也就是它的“高度”。每当它乘以上一个高度的值是真正地最小值时，就将它的高度+1，其它数字的高度保持不变。好了，清楚了逻辑，我们就可以上代码了。

public static int nthSuperUglyNumber(int n,int[] primers){
        int[] times=new int[primers.length];
        int[] uglynumbers=new int[n];
        uglynumbers[0]=1;
        for(int i=1;i<n;i++){
            int min=Integer.MAX_VALUE;
            for(int j=0;j<primers.length;j++){
                min=Math.min(min,primers[j]*uglynumbers[times[j]]);
            }
            uglynumbers[i]=min;
        for(int j=0;j<times.length;j++){
            if(primers[j]*uglynumbers[times[j]]==min){
                times[j]++;
            }
        }
        }
        return uglynumbers[n-1];
    }

昨天去学校图书馆，坐下来才发现没有带草稿本，于是就在那里干想，想了很久，还是画图好理解一点。