首页 > 代码库 > LeetCode-Super Ugly Number

LeetCode-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.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Analysis:

Similar to Ugly Number II, but maintain a heap + a index map to perform O(log(k)) look up of minimum values.

NOTE: While theoretically the complexity is O(Nlog(k)), in reality, it may be slower than a O(NK) solution using primitive data structure like in[], because this solution use high-level data structures like PQ and HashMap.

Solution:

public class Solution {    public int nthSuperUglyNumber(int n, int[] primes) {        if (n==1) return 1;        if (primes.length==0) return -1;                int[] nums = new int[n];        nums[0] = 1;        int[] pList = new int[primes.length];        Arrays.fill(pList,0);        PriorityQueue<Integer> values = new PriorityQueue<Integer>();        HashMap<Integer,List<Integer>> valueMap = new HashMap<Integer,List<Integer>>();                for (int i=0;i<pList.length;i++){            addValue(primes,nums,values,valueMap,pList,i);        }                for (int i=1;i<n;i++){            // Get the min value            int minVal = values.poll();            nums[i] = minVal;                        List<Integer> pointers = valueMap.get(minVal);            valueMap.remove(minVal);            for (int p : pointers){                pList[p]++;                addValue(primes,nums,values,valueMap,pList,p);            }        }        return nums[n-1];    }        public void addValue(int[] primes, int[] nums, PriorityQueue<Integer> values, HashMap<Integer,List<Integer>> valueMap, int[] pList, int index){        int val = nums[pList[index]]*primes[index];        if (!valueMap.containsKey(val)){            valueMap.put(val,new ArrayList<Integer>());            values.add(val);         }        valueMap.get(val).add(index);    }}

 

LeetCode-Super Ugly Number