LeetCode 题解：剑指 Offer 49. 丑数，三指针，JavaScript，详细注释

Lee Chen

关注

发布于: 2021 年 04 月 14 日

LeetCode题解：剑指 Offer 49. 丑数，三指针，JavaScript，详细注释

原题链接：剑指 Offer 49. 丑数

解题思路：

参考了详细通俗的思路分析，多解法中的解法三。
在使用堆的解法中，每一个丑数都是由之前最小的丑数分别乘以 2、3、5 计算而来，生成的序列如下：

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …

如果将其拆分则是下面这样的：

1, 1×2, 1×3, 2×2, 1×5, 2×3, 2×4, 3×3, 3×4, 3×5...

按照上面的规律，可以将其按照各个质因数将其拆分成下面三组：

乘 2: 1×2, 2×2, 3×2, 4×2, 5×2, 6×2, 8×2, 9×2,…乘 3: 1×3, 2×3, 3×3, 4×3, 5×3, 6×3, 8×3, 9×3,…乘 5: 1×5, 2×5, 3×5, 4×5, 5×5, 6×5, 8×5, 9×5,…

复制代码

我们可以注意到，被乘数的规律和丑数是一样的。

我们可以使用三个指针，分别表示上面三组的被乘数在丑数序列中的位置，也就知道了它当前所需要进行的计算。例如当前乘 2 指针指向的是丑数 5，就表示当前乘 2 指针需要进行5×2运算。
三个指针分别计算出的结果，取最小值，就是下一个丑数的值。同时这个被取最小值的运算，才是当前真实要实行的运算，因此要将对应的指针向前移动一位。
这样循环计算可以保证每次计算的结果都是最优的，也就保证了丑数从小到大的排列顺序，这样计算 n 次就得到了第 n 个丑数。

/** * @param {number} n * @return {number} */var nthUglyNumber = function (n) {  let ugly = [1]; // 使用数组按从小到大顺序存储丑数，初始值为1保证了循环能够正常启动  // 质因数包含2、3、5的丑数在ugly数组中的位置指针  let index3 = 0;  let index2 = 0;  let index5 = 0;
  // 循环生成n个丑数，并存入数组  for (let i = 1; i < n; i++) {    // 分别以当前2、3、5质因数对应的丑数为基础，计算下一组丑数    const newUgly2 = ugly[index2] * 2;    const newUgly3 = ugly[index3] * 3;    const newUgly5 = ugly[index5] * 5;    // 将新的一组丑数取最小值，即为新的一个丑数    const minUgly = Math.min(newUgly2, newUgly3, newUgly5);    // 将新丑数存入丑数数组，保证了ugly数组从小到大排列    ugly.push(minUgly);
    // 只有新一组丑数中，值恰好为最小的指针才需要移动    if (newUgly2 === minUgly) {      index2++;    }    if (newUgly3 === minUgly) {      index3++;    }    if (newUgly5 === minUgly) {      index5++;    }  }
  // ugly数组的最后一个值，即为第n个丑数  return ugly[ugly.length - 1];};

复制代码

发布于: 2021 年 04 月 14 日阅读数: 12

原文链接:【http://xie.infoq.cn/article/6ead87c39b81bd145e14e039f】。文章转载请联系作者。

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

发布

暂无评论

创作场景

LeetCode 题解：剑指 Offer 49. 丑数，三指针，JavaScript，详细注释

Lee Chen

评论