写点什么

LeetCode 题解:剑指 Offer 49. 丑数,暴力法,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 03 月 26 日
LeetCode题解:剑指 Offer 49. 丑数,暴力法,JavaScript,详细注释

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


解题思路:


  1. 使用三个嵌套循环,计算出所有可能的丑数。

  2. 由于每层循环都是在上层循环的结果基础上进行计算,因此计算结果并未排序。

  3. 将所有丑数从小到大排序,再取出第 n 个即可。


/** * @param {number} n * @return {number} */var nthUglyNumber = function (n) {  let ugly = []; // 存储所有的丑数
// 分别枚举所有质因数为2、3、5的数,将其存入数组 // 0x7FFFFFFF即为最大的32位二进制数,即0b1111111111111111111111111111111 // 对应的是10进制数2147483647,计算出的丑数长度为1691 for (let i = 1; i <= 0x7fffffff; i *= 2) { for (let j = i; j <= 0x7fffffff; j *= 3) { for (let k = j; k <= 0x7fffffff; k *= 5) { ugly.push(k); } } }
// 由于每层循环都是在上层循环的结果基础上进行计算,例如在i和j都等于1的情况下,先计算了所有k*=5的结果 // 用此方法计算出的丑数并不是按大小排序,因此只能将所有丑数计算出来,再进行排序取需要的值 ugly.sort((a, b) => a - b);
// 取出第n个丑数 return ugly[n - 1];};
复制代码


发布于: 2021 年 03 月 26 日阅读数: 7
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:剑指 Offer 49. 丑数,暴力法,JavaScript,详细注释