Super Ugly Number

描述

Write a function to find the n-th 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 is a super ugly number for any given primes.
  • The given numbers in primes are in ascending order.
  • 0 < k ≤ 100, 0 < n ≤ 1000000, 0 < primes[i] < 1000.

    分析

这题是 Ugly Number II 的扩展。在"Ugly Number II"中，primes=[2,3,5]，这题中primes可以自由变化。

所以这题可以用"Ugly Number II"的思路解决。每次要从多个列表中选择最小的元素，我们可以维护一个大小为primes长度的小根堆。

代码

  1. // Super Ugly Number
  2. // Time complexity: O(n), Space complexity: O(n)
  3. public class Solution {
  4.     public int nthSuperUglyNumber(int n, int[] primes) {
  5.         final int[] nums = new int[n];
  6.         nums[0] = 1; // 1 is the first ugly number
  7.         final Queue<Node> q = new PriorityQueue<>();
  8.         for (int i = 0; i < primes.length; ++i) {
  9.             q.add(new Node(0, primes[i], primes[i]));
  10.         }
  12.         for (int i = 1; i < n; ++i) {
  13.             // get the min element and add to nums
  14.             Node node = q.peek();
  15.             nums[i] = node.val;
  17.             // update top elements
  18.             do {
  19.                 node = q.poll();
  20.                 node.val = nums[++node.index] * node.prime;
  21.                 q.add(node); // push it back
  22.                 // prevent duplicate
  23.             } while (!q.isEmpty() && q.peek().val == nums[i]);
  24.         }
  25.         return nums[n - 1];
  26.     }
  27.     static class Node implements Comparable<Node> {
  28.         private int index;
  29.         private int val;
  30.         private int prime;
  32.         public Node(int index, int val, int prime) {
  33.             this.index = index;
  34.             this.val = val;
  35.             this.prime = prime;
  36.         }
  37.         public int compareTo(Node other) {
  38.             return this.val - other.val;
  39.         }
  40.     }
  41. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/number-theory/super-ugly-number.html