本文共 3133 字,大约阅读时间需要 10 分钟。
和ugly number II的思路很类似,要使得super ugly number 不漏掉,那么用每个因子去乘第一个,当前因子乘积是最小后,乘以下一个…..以此类推。
python令人难以接受的代码实现:
class Solution(object): def nthSuperUglyNumber(self, n, primes): """ :type n: int :type primes: List[int] :rtype: int """ if n == 1: return 1 if primes == None or len(primes) == 0: return n length = len(primes) index = [1] * length dp = [1] * (n + 1) dp[1] = 1 factor = copy.deepcopy(primes) for i in range(2, n + 1): factor_index = self.getIndexOfMin(factor) dp[i] = factor[factor_index] self.handleEqualFactors(factor_index, dp[i], factor, index, dp, primes) index[factor_index] += 1 factor[factor_index] = primes[factor_index] * dp[index[factor_index]] return dp[n] def handleEqualFactors(self, factor_index, value, factor, index, dp, primes): length = len(factor) for i in range(factor_index + 1, length): if factor[i] == value: index[i] += 1 factor[i] = primes[i] * dp[index[i]] def getIndexOfMin(self, factor): length = len(factor) index = 0 cur_min = factor[0] for i in range(1, length): if factor[i] < cur_min: cur_min = factor[i] index = i return indexpython heapq实现:()
import heapqclass Solution(object): def nthSuperUglyNumber(self, n, primes): """ :type n: int :type primes: List[int] :rtype: int """ length = len(primes) idx = [0] * length ans = [1] minlist = [(primes[i]*ans[idx[i]], i) for i in xrange(len(idx))] #[(val, idx),(),...],这里把val和idx算作tuple算进去。 heapq.heapify(minlist) while len(ans) < n: (umin, min_idx) = heapq.heappop(minlist) idx[min_idx] += 1 if umin != ans[-1]: ans.append(umin) heapq.heappush(minlist, (primes[min_idx]*ans[idx[min_idx]], min_idx)) return ans[-1]
java优先队列版本:()
// http://www.hrwhisper.me/leetcode-super-ugly-number/public class Solution { public int nthSuperUglyNumber(int n, int[] primes) { int[] ugly_number = new int[n]; ugly_number[0] = 1; PriorityQueueq = new PriorityQueue (); for (int i = 0; i < primes.length; i++) q.add(new Node(0, primes[i], primes[i])); for (int i = 1; i < n; i++) { Node cur = q.peek(); ugly_number[i] = cur.val; do { cur = q.poll(); cur.val = ugly_number[++cur.index] * cur.prime; q.add(cur); } while (!q.isEmpty() && q.peek().val == ugly_number[i]); } return ugly_number[n - 1]; }}class Node implements Comparable { int index; int val; int prime; Node(int index, int val, int prime) { this.val = val; this.index = index; this.prime = prime; } public int compareTo(Node x) { return this.val > x.val ? 1 : -1; }}
转载地址:http://pmbvb.baihongyu.com/