丑数
解题思路：
-
首先 1 是丑数, 那么 1 乘以 2,3,5 得到的乘积也肯定是丑数(根据丑数的定义可知), 也就是说每一个已知的丑数, 乘上 2,3,5 之后都会得到 3 个更大的丑数(可能有重复)；
-
由于题目要求丑数的顺序是从小到大排序, 那么就把已知的丑数先写出来, 每个丑数占一行, 而和 2、3、5 的乘积的丑数就作为列, 放到同一行上, 如下所示：
- 1 「2 3 5」，这一行里 2、3、5 分别是 1 的三个乘积；
- 2 「4 6 10」，这一行里 4、6、10 是 2 的三个乘积；
- 3 「6 9 15」，这一行里 6、9、15 是 3 的三个乘积；
- 4 「8 12 20」，…
-
观察上面的矩阵可以轻松发现, 每一个数组都是从左往右递增, 从上往下递增, 可以设置三个指针, 分别指向第 0行的 1、2、3 列(行列数从 0 开始算)；
-
之后只要把三个指针所在位置的元素做个对比, 取最小的那个元素, 就是下一个丑数了，然后和 2、3、5 的乘积求出这一行的丑数；
- 1 「2 3 5」，a=2（索引为 0）、b=3（索引为 0）、c=5（索引为 0），2 为下一列的丑数，a 索引为 1；
- 2 「4 6 10」，a=4（索引为 1）、b=3（索引为 0）、c=5（索引为 0），3 为下一列的丑数，b 索引为 1；
- 3 「6 9 15」，a=4（索引为 1）、b=6（索引为 1）、c=5（索引为 0），4 为下一列的丑数，a 索引为 2；
- 4 「8 12 20」，…
-
接着在三个指针里找到最小的丑数的指针， 这个指针必须往下移动 1 位, 把计算的丑数放入丑数数组中, 继续计算下一个丑数, 直到算出第 N 个丑数出来即可；
复杂度：
-
时间复杂度：O(n)，需要计算数组 dp 中的 n 个元素，每个元素的计算都可以在 O(1) 的时间内完成；
-
空间复杂度：O(n)，空间复杂度主要取决于数组 dp 的大小；
代码实现：
function nthUglyNumber(n: number): number {
let dp: number[] = [1];
// 3 列索引
let a: number = 0, b: number = 0, c: number = 0;
for (let i = 1; i < n; i++) {
let n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
dp[i] = Math.min(n2, n3, n5);
if (dp[i] == n2) a++;
if (dp[i] == n3) b++;
if (dp[i] == n5) c++;
}
return dp[n - 1];
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
webpack 核心功能👉 如何在浏览器端实现模块化
上一篇
评论
