[LeetCode] 313. Super Ugly Number 超级丑陋数

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 313. Super Ugly Number 超级丑陋数,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Write a program to find the nth super ugly number.html

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.java

Example:python

Input: n = 12, primes = [2,7,13,19]
Output: 32 
Explanation: [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 is a super ugly number for any given primes.
  • The given numbers in primes are in ascending order.
  • 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
  • The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

264. Ugly Number II 的拓展,仍是找出第n个丑陋数,但质数集合不在只是2,3,5,而是能够任意给定。难度增长了,但本质上和Ugly Number II 没有什么区别,因为不知道质数的个数,能够用一个idx数组来保存当前的位置,而后从每一个子链中取出一个数,找出其中最小值,而后更新idx数组对应位置,注意有可能最小值不止一个,要更新全部最小值的位置。app

解题思路:
要使得super ugly number不漏掉,那么须要使用每一个因子去乘以其对应的“第一个”丑数。那么何为对应的“第一个”丑数?ide

首先,利用ugly[]数组来保存全部的超级丑数,ugly[i]表示第i+1个超级丑数;post

接着利用pointer[]数组来表示每一个因子对应的“第一个”丑数的下标。pointer数组长度固然须要和primes长度一致,且初始化为0,表明着每一个因子对应的“第一个”丑数都是ugly[0];this

接下来咱们以primes[2,7,13,19],pointer[0,0,0,0],ugly[0]=1做为初始条件往下看:url

遍历primes数组,用每一个因子都乘以其对应的第一个丑数,即ugly[0]=1,能够发现1x2=2是最小值,故ugly[1]=2;但要注意,此时的pointer数组发生了变化:code

因为当前产生的丑数2是由2这个因子乘以它的对应“第一个”丑数获得的,所以须要将pointer[0]加一。pointer[0]是2这个因子对应的“第一个”丑数的下标,由于当前已经使用了2x1,若是不更新,则下一轮仍是会用2这个因子去乘以第一个丑数(ugly[0]).将其更新后,则意味着2这个因子对应的第一个丑数已经改变了,变成了ugly[1].而其余三个对应的“第一个”丑数仍是ugly[0]。

咱们接着看下一轮:2x2【即ugly[pointer[1]]x2】,1x7,1x13,1x19,发现仍是2这个因子获得的数最小,故更新:ugly[2]=2x2=4,pointer[0]=2;

下一轮:4x2,1x7,1x13,1x19,能够发现当前这一轮最小值是7,且由因子7产生,故更新:ugly[3]=7,pointer[1]=1;

以此类推....
若是更新过程当中,出现最小值不止一个的话,则其对应的pointer的值都须要增长1。

Java:

public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n+1];
        ugly[0]=1;
        int[] pointer = new int[primes.length];
        for(int i=1;i<n;i++) {
            int min=Integer.MAX_VALUE;
            int minIndex = 0;
            for(int j=0;j<primes.length;j++) {
                if(ugly[pointer[j]]*primes[j]<min) {
                    min=ugly[pointer[j]]*primes[j];
                    minIndex = j;
                }else if(ugly[pointer[j]]*primes[j]==min) {
                    pointer[j]++;
                }
            }
            ugly[i]=min;
            pointer[minIndex]++;
        }
        return ugly[n-1];
    }

Java:1

public int nthSuperUglyNumberI(int n, int[] primes) {
    int[] ugly = new int[n];
    int[] idx = new int[primes.length];

    ugly[0] = 1;
    for (int i = 1; i < n; i++) {
        //find next
        ugly[i] = Integer.MAX_VALUE;
        for (int j = 0; j < primes.length; j++)
            ugly[i] = Math.min(ugly[i], primes[j] * ugly[idx[j]]);
        
        //slip duplicate
        for (int j = 0; j < primes.length; j++) {
            while (primes[j] * ugly[idx[j]] <= ugly[i]) idx[j]++;
        }
    }

    return ugly[n - 1];
}

Java:2

public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n];
        int[] idx = new int[primes.length];
        int[] val = new int[primes.length];
        Arrays.fill(val, 1);

        int next = 1;
        for (int i = 0; i < n; i++) {
            ugly[i] = next;
            
            next = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; j++) {
                //skip duplicate and avoid extra multiplication
                if (val[j] == ugly[i]) val[j] = ugly[idx[j]++] * primes[j];
                //find next ugly number
                next = Math.min(next, val[j]);
            }
        }

        return ugly[n - 1];
    }

Java: 3 index heap 

public int nthSuperUglyNumberHeap(int n, int[] primes) {
    int[] ugly = new int[n];

    PriorityQueue<Num> pq = new PriorityQueue<>();
    for (int i = 0; i < primes.length; i++) pq.add(new Num(primes[i], 1, primes[i]));
    ugly[0] = 1;

    for (int i = 1; i < n; i++) {
        ugly[i] = pq.peek().val;
        while (pq.peek().val == ugly[i]) {
            Num nxt = pq.poll();
            pq.add(new Num(nxt.p * ugly[nxt.idx], nxt.idx + 1, nxt.p));
        }
    }

    return ugly[n - 1];
}

private class Num implements Comparable<Num> {
    int val;
    int idx;
    int p;

    public Num(int val, int idx, int p) {
        this.val = val;
        this.idx = idx;
        this.p = p;
    }

    @Override
    public int compareTo(Num that) {
        return this.val - that.val;
    }
} 

Python:

def nthSuperUglyNumber(self, n, primes):
        ugly = [1]
        pointers = [0]*len(primes)
        
        for i in range(1,n):
            minu = float("inf")
            minIndex = 0
            for j in range(len(primes)):
                if primes[j] * ugly[pointers[j]] < minu:
                    minu = primes[j] * ugly[pointers[j]]
                    minIndex = j
                elif primes[j] * ugly[pointers[j]] == minu:
                    pointers[j] += 1
            ugly.append(minu)
            pointers[minIndex] += 1
        return ugly[-1]  

Python:

# Heap solution. (620ms)
class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        heap, uglies, idx, ugly_by_last_prime = [], [0] * n, [0] * len(primes), [0] * n
        uglies[0] = 1

        for k, p in enumerate(primes):
            heapq.heappush(heap, (p, k))

        for i in xrange(1, n):
            uglies[i], k = heapq.heappop(heap)
            ugly_by_last_prime[i] = k
            idx[k] += 1
            while ugly_by_last_prime[idx[k]] > k:
                idx[k] += 1
            heapq.heappush(heap, (primes[k] * uglies[idx[k]], k))

        return uglies[-1]

Python:

# Time:  O(n * k)
# Space: O(n + k)
# Hash solution. (932ms)
class Solution2(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        uglies, idx, heap, ugly_set = [0] * n, [0] * len(primes), [], set([1])
        uglies[0] = 1

        for k, p in enumerate(primes):
            heapq.heappush(heap, (p, k))
            ugly_set.add(p)

        for i in xrange(1, n):
            uglies[i], k = heapq.heappop(heap)
            while (primes[k] * uglies[idx[k]]) in ugly_set:
                idx[k] += 1
            heapq.heappush(heap, (primes[k] * uglies[idx[k]], k))
            ugly_set.add(primes[k] * uglies[idx[k]])

        return uglies[-1]

Python:  

# Time:  O(n * logk) ~ O(n * klogk)
# Space: O(n + k)
class Solution3(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        uglies, idx, heap = [1], [0] * len(primes), []
        for k, p in enumerate(primes):
            heapq.heappush(heap, (p, k))

        for i in xrange(1, n):
            min_val, k = heap[0]
            uglies += [min_val]

            while heap[0][0] == min_val:  # worst time: O(klogk)
                min_val, k = heapq.heappop(heap)
                idx[k] += 1
                heapq.heappush(heap, (primes[k] * uglies[idx[k]], k))

        return uglies[-1]    

C++:

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> res(1, 1), idx(primes.size(), 0);
        while (res.size() < n) {
            vector<int> tmp;
            int mn = INT_MAX;
            for (int i = 0; i < primes.size(); ++i) {
                tmp.push_back(res[idx[i]] * primes[i]);
            }
            for (int i = 0; i < primes.size(); ++i) {
                mn = min(mn, tmp[i]);
            }
            for (int i = 0; i < primes.size(); ++i) {
                if (mn == tmp[i]) ++idx[i];
            }
            res.push_back(mn);
        }
        return res.back();
    }
};

C++:  

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> dp(n, 1), idx(primes.size(), 0);
        for (int i = 1; i < n; ++i) {
            dp[i] = INT_MAX;
            for (int j = 0; j < primes.size(); ++j) {
                dp[i] = min(dp[i], dp[idx[j]] * primes[j]);
            }
            for (int j = 0; j < primes.size(); ++j) {
                if (dp[i] == dp[idx[j]] * primes[j]) {
                    ++idx[j];
                }
            }
        }
        return dp.back();
    }
};

  

 

相似题目:

[LeetCode] 263. Ugly Number 丑陋数

[LeetCode] 264. Ugly Number II 丑陋数 II

 

All LeetCode Questions List 题目汇总