264. 丑数 II

给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：
输入：n = 10 输出：12 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：
输入：n = 1 输出：1 解释：1 通常被视为丑数。

提示：

  • 1 <= n <= 1690

思路：
方法一：使用优先队列 + 集合去重
方法二：使用多路归并，本质上是DP

  1. // 多路归并
  2. class Solution {
  3.     public int nthUglyNumber(int n) {
  4.         int[] p = new int[n];
  5.         p[0] = 1;
  6.         int x = 0, y = 0, z = 0;
  8.         for (int i = 1; i < n; i++) {
  9.             int a = p[x] * 2, b = p[y] * 3, c = p[z] * 5;
  10.             int min = Math.min(a, Math.min(b, c));
  11.             if (a == min) x++;
  12.             if (b == min) y++;
  13.             if (c == min) z++;
  14.             p[i] = min;
  15.         }
  16.         return p[n - 1];
  17.     }
  18. }

313. 超级丑数

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。
题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

示例 1：
输入：n = 12, primes = [2,7,13,19] 输出：32 解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

示例 2：
输入：n = 1, primes = [2,3,5] 输出：1 解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。
提示：

  • 1 <= n <= 106
  • 1 <= primes.length <= 100
  • 2 <= primes[i] <= 1000
  • 题目数据 保证 primes[i] 是一个质数
  • primes 中的所有值都 互不相同 ，且按 递增顺序 排列
  1. // 暴力多路归并
  2. class Solution {
  3.     public int nthSuperUglyNumber(int n, int[] primes) {
  4.         int[] res = new int[n];
  5.         res[0] = 1;
  6.         int[] p = new int[primes.length];
  8.         for (int i = 1; i < n; i++) {
  9.             int min = Integer.MAX_VALUE;
  10.             for (int j = 0; j < p.length; j++) {
  11.                 if (res[p[j]] * primes[j] < min)
  12.                     min = res[p[j]] * primes[j];
  13.             }
  14.             res[i] = min;
  15.             for (int j = 0; j < p.length; j++)
  16.                 if (res[p[j]] * primes[j] == min)
  17.                     p[j]++;
  18.         }
  19.         return res[n - 1];
  20.     }
  21. }
  1. // 堆优化的多路归并
  2. class Solution {
  3.     public int nthSuperUglyNumber(int n, int[] primes) {
  4.         PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> (o1[0] - o2[0]));
  5.         for (int i = 0; i < primes.length; i++) {
  6.             q.offer(new int[]{primes[i], i, 1});
  7.         }
  8.         int[] res = new int[n];
  9.         res[0] = 1;
  10.         for (int i = 1; i < n;) {
  11.             int[] p = q.poll();
  12.             if (p[0] != res[i - 1]) res[i++] = p[0];
  13.             q.offer(new int[]{res[p[2]] * primes[p[1]], p[1], p[2] + 1});
  14.         }
  15.         return res[n - 1];
  16.     }
  17. }

986. 区间列表的交集

二路归并