题目形容
这是 LeetCode 上的 面试题 17.09. 第 k 个数 ，难度为 艰难。
Tag : 「优先队列（堆）」、「多路归并」、「双指针」
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。留神，不是必须有这些素因子，而是必须不蕴含其余的素因子。例如，前几个数按程序应该是 1，3，5，7，9，15，21。
示例 1:
输出: k = 5输入: 9根本剖析
本题的基本思路与 264. 丑数 II : 从奢侈优先队列到多路归并 完全一致。
优先队列（小根堆）
有了根本的剖析思路，一个简略的解法是应用优先队列：
- 起始先将最小数值 $1$ 放入队列
- 每次从队列取出最小值 $x$，而后将 $x$ 所对应的数值 $3x$、$5x$ 和 $7x$ 进行入队
- 对步骤 2 循环屡次，第 $k$ 次出队的值即是答案
为了避免同一数值屡次进队，咱们须要应用数据结构 $Set$ 来记录入过队列的数值。
Java 代码：
class Solution { public int getKthMagicNumber(int k) { int[] nums = new int[]{3, 5, 7}; PriorityQueue<Long> q = new PriorityQueue<>(); Set<Long> set = new HashSet<>(); q.add(1L); set.add(1L); while (!q.isEmpty()) { long t = q.poll(); if (--k == 0) return (int) t; for (int x : nums) { if (!set.contains(x * t)) { q.add(x * t); set.add(x * t); } } } return -1; }}Python3 代码：
class Solution: def getKthMagicNumber(self, k: int) -> int: nums = [3, 5, 7] q, vis = [], set() q.append(1) vis.add(1) while q: t = heapq.heappop(q) k -= 1 if k == 0: return t for x in nums: if t * x not in vis: heapq.heappush(q, t * x) vis.add(t * x) return -1- 工夫复杂度：$O(k\log{k})$
- 空间复杂度：$O(k)$
多路归并（多指针）
从解法一中不难发现，咱们「往后产生的数值」都是基于「已有数值」而来（应用「已有数值」乘上 $3$、$5$、$7$）。
因而，如果咱们最终的数值序列为 $a1,a2,a3,...,an$ 的话，序列中的每一个数都必然可能被以下三个序列（中的至多一个）笼罩：
- 由数值 $\times 3$ 所得的有序序列：$1 \times 3$、$2 \times 3$、$3 \times 3$、$4 \times 3$、$5 \times 3$、$6 \times 3$、$8 \times 3$ ...
- 由数值 $\times 5$ 所得的有序序列：$1 \times 5$、$2 \times 5$、$3 \times 5$、$4 \times 5$、$5 \times 5$、$6 \times 5$、$8 \times 5$ ...
- 由数值 $\times 6$ 所得的有序序列：$1 \times 7$、$2 \times 7$、$3 \times 7$、$4 \times 7$、$5 \times 7$、$6 \times 7$、$8 \times 6$ ...
举个，假如咱们须要求得 $[1, 3, 5, 7, 9, 15, 21]$ 数值序列 $arr$ 的最初一位，那么该序列能够看作以下三个有序序列归并而来：
- $1 \times 3, 3 \times 3, 5 \times 3, ... , 15 \times 3, 21 \times 3$ ，将 $3$ 提出，即 $arr \times 3$
- $1 \times 5, 3 \times 5, 5 \times 5, ... , 15 \times 5, 21 \times 5$ ，将 $5$ 提出，即 $arr \times 5$
- $1 \times 7, 3 \times 7, 5 \times 7, ... , 15 \times 7, 21 \times 7$ ，将 $7$ 提出，即 $arr \times 7$
因而咱们能够应用三个指针来指向指标序列 $arr$ 的某个下标（下标 $0$ 作为哨兵不应用，起始都为 $1$），应用 $arr[下标] \times 系数$（3、5 和 7） 代表以后应用到三个有序序列中的哪一位，同时应用 $idx$ 示意以后生成到 $arr$ 哪一位数值。
Java 代码：
class Solution { public int getKthMagicNumber(int k) { int[] ans = new int[k + 1]; ans[1] = 1; for (int i3 = 1, i5 = 1, i7 = 1, idx = 2; idx <= k; idx++) { int a = ans[i3] * 3, b = ans[i5] * 5, c = ans[i7] * 7; int min = Math.min(a, Math.min(b, c)); if (min == a) i3++; if (min == b) i5++; if (min == c) i7++; ans[idx] = min; } return ans[k]; }}TypeScript 代码：
function getKthMagicNumber(k: number): number { const ans = new Array<number>(k + 1).fill(1) for (let i3 = 1, i5 = 1, i7 = 1, idx = 2; idx <= k; idx++) { const a = ans[i3] * 3, b = ans[i5] * 5, c = ans[i7] * 7 const min = Math.min(a, Math.min(b, c)) if (a == min) i3++ if (b == min) i5++ if (c == min) i7++ ans[idx] = min } return ans[k]};Python 代码：
class Solution: def getKthMagicNumber(self, k: int) -> int: ans = [1] * (k + 1) i3, i5, i7 = 1, 1, 1 for idx in range(2, k + 1): a, b, c = ans[i3] * 3, ans[i5] * 5, ans[i7] * 7 cur = min([a, b, c]) i3 = i3 + 1 if cur == a else i3 i5 = i5 + 1 if cur == b else i5 i7 = i7 + 1 if cur == c else i7 ans[idx] = cur return ans[k]- 工夫复杂度：$O(k)$
- 空间复杂度：$O(k)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.面试题 17.09 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布