LC 面试题 17.09. 第 k 个数

题目描述

这是 LeetCode 上的 面试题 17.09. 第 k 个数 ,难度为 困难

有些数的素因子只有 357,请设计一个算法找出第 k 个数。注意,不是必须有这些素因子,而是必须不包含其他的素因子。例如,前几个数按顺序应该是 135791521

示例 1:

1
2
3
输入: k = 5

输出: 9


基本分析

本题的基本思路与 264. 丑数 II : 从朴素优先队列到多路归并 完全一致。


优先队列(小根堆)

有了基本的分析思路,一个简单的解法是使用优先队列:

  1. 起始先将最小数值 $1$ 放入队列
  2. 每次从队列取出最小值 $x$,然后将 $x$ 所对应的数值 $3x$、$5x$ 和 $7x$ 进行入队
  3. 对步骤 2 循环多次,第 $k$ 次出队的值即是答案

为了防止同一数值多次进队,我们需要使用数据结构 $Set$ 来记录入过队列的数值。

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 系数$(357) 代表当前使用到三个有序序列中的哪一位,同时使用 $idx$ 表示当前生成到 $arr$ 哪一位数值。

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 代码:
1
2
3
4
5
6
7
8
9
10
11
12
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 代码:
1
2
3
4
5
6
7
8
9
10
11
12
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/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。