超级丑数 [英] Super Ugly Number

问题描述

所以问题是:

编写程序以查找第n个超级丑陋的数字.

Write a program to find the nth super ugly number.

超级丑数是正数，其所有素数均在给定的素数列表k素数中.例如，[1、2、4、7、8、13、14、16、19、26、28、32]是给定素数= [2、7、13、19]的前12个超级丑数的序列大小为4.

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.

因此，我的算法基本上使用它们遵循的模式找到所有可能的因素，将它们推入数组，对该数组进行排序，然后返回数组中的第n个值.它可以精确地计算所有参数，但是对于第n个较高的值来说速度太慢.

So my algorithm basically finds all possible factors using the pattern they follow, pushes them to an array, sorts that array and then returns the nth value in the array. It accurately calculates all of them, however, is too slow with high nth values.

我的问题是执行此操作的正确方法是什么，因为我确信必须有一个更直接的解决方案.我最想知道找到它的背后的理论以及对此是否有某种封闭的公式.

My question is what the proper way to do this is as I'm sure there has to be a more straightforward solution. I'm mostly curious about the theory behind finding it and if there's some kind of closed formula for this.

 var nthSuperUglyNumber = function(n, primes) {
     xprimes = primes;
     var uglies = [1];
     uglies = getUglyNumbers(n, primes, uglies);
     // return uglies[n-1];
     return uglies[n - 1];
 };

 //                     3                         4
 //1, 2,3,5, || 4,6,10, 9,15, 25, || 8,12,20,18,30,50, 27,45,75, 125 ||
 //   3,2,1     6,3,1,               10,4,1
 //              1            1              1
 //1, 2,3 || 4,6, 9, || 8,12,18, 27 || 16,24,36,54, 81
 //   2,1    3,1        4,1            5,1
 //
 //1, 2,3,5,7 || 4,6,10,14 9,15,21 25,35, 49 ||
 //   4,3,2,1 || 10,6,3,1

 var getUglyNumbers = function(n, primes, uglies) {
     if (n == 1) {
         return uglies;
     }
     var incrFactor = [];

     var j = 0;
     // Initial factor and uglies setup
     for (; j < primes.length; j += 1) {
         incrFactor[j] = primes.length - j;
         uglies.push(primes[j]);
     }

     //recrusive algo
     uglies = calcUglies(n, uglies, incrFactor);
     uglies.sort(function(a, b) {
     return a - b;
     });
     return uglies;
 };

 var calcUglies = function(n, uglies, incrFactor) {
     if (uglies.length >= 5 * n) return uglies;
     var currlength = uglies.length;
     var j = 0;
     for (j = 0; j < xprimes.length; j += 1) {
         var i = 0;
         var start = currlength - incrFactor[j];
         for (i = start; i < currlength; i += 1) {
             uglies.push(xprimes[j] * uglies[i]);
         }
     }
     // Upgrades the factors to level 2
     for (j = 1; j < xprimes.length; j += 1) {
         incrFactor[xprimes.length - 1 - j] = incrFactor[xprimes.length - j] + incrFactor[xprimes.length - 1 - j];
     }

     return calcUglies(n, uglies, incrFactor);
 };

推荐答案

public static ArrayList<Integer> superUgly(int[] primes,int size)
{
    Arrays.sort(primes);
    int pLen = primes.length;

    ArrayList<Integer> ans = new ArrayList<>();
    ans.add(1);

    PriorityQueue<pair> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(p -> p.value));
    HashSet<Integer> hashSet = new HashSet<>();

    int next_ugly_number;
    int[] indices = new int[pLen];

    for(int i=0;i<pLen;i++) {
        hashSet.add(primes[i]);
        priorityQueue.add(new pair(i,primes[i]));
    }

    while(ans.size()!=size+1)
    {
        pair pair = priorityQueue.poll();
        next_ugly_number = pair.value;
        ans.add(next_ugly_number);
        indices[pair.index]+=1;

        int temp = ans.get(indices[pair.index])*primes[pair.index];
        if (!hashSet.contains(temp))
        {
            priorityQueue.add(new pair(pair.index,temp));
            hashSet.add(temp);
        }
        else {
            while(hashSet.contains(temp))
            {
                indices[pair.index]+=1;
                 temp = ans.get(indices[pair.index])*primes[pair.index];

            }
            priorityQueue.add(new pair(pair.index,temp));
            hashSet.add(temp);

        }

    }

    ans.remove(0);
    return ans;
}

配对是

class pair
{
    int index,value;
    public pair(int i,int v)
    {
        index = i;
        value = v;
    }
}

它返回大小为'size'的丑陋数字列表.
我正在使用优先级队列来查找每个循环的最小值，并使用一个哈希集来避免在priorityQueue中重复条目.
因此，它的时间复杂度为O(n log(k))，其中n是大小，而k是素数数组大小.

It returns a list of ugly numbers of size 'size'.
I am using priority queue to find minimum for every loop and also a hashset to avoid duplicate entries in priorityQueue.
So its time complexity is O(n log(k)) where n is size and k is primes array size.

这篇关于超级丑数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！