前端进阶之旅前端进阶之旅
基础篇
进阶篇
高频篇
精选篇
手写篇
原理篇
面经篇
AI 面试
自检篇
每日一题
  • 综合
    • 综合题型
    • 其他问题
    • 设计模式
    • 思维导图
    • 学习路线
  • 前端基础
    • HTTP
    • 浏览器
    • 计算机基础
  • 进阶学习
    • NPM工作流
    • Docker
    • Canvas
    • Node学习指南
    • 前端综合文章
  • 其他
    • Handbook
    • 职场话题
    • CSS可视化
小程序题库
公众号动态
博客动态
开发者导航
基础篇
进阶篇
高频篇
精选篇
手写篇
原理篇
面经篇
AI 面试
自检篇
每日一题
  • 综合
    • 综合题型
    • 其他问题
    • 设计模式
    • 思维导图
    • 学习路线
  • 前端基础
    • HTTP
    • 浏览器
    • 计算机基础
  • 进阶学习
    • NPM工作流
    • Docker
    • Canvas
    • Node学习指南
    • 前端综合文章
  • 其他
    • Handbook
    • 职场话题
    • CSS可视化
小程序题库
公众号动态
博客动态
开发者导航
  • React专栏

    • React组合式开发实战

      • 前端开发的四个时代
      • 企业管理系统的前世今生
      • 可视化页面搭建工具
      • 实战篇 01:开发前准备
      • 实战篇 02:项目脚手架
      • 实战篇 03:页面布局方案
      • 实战篇 04:权限管理机制
      • 实战篇 05:菜单匹配逻辑
      • 实战篇 06:消息通知设计
      • 实战篇 07:多语言支持
      • 继往开来:可视化页面搭建工具
    • React Hooks与Immutable实战

    • React SSR服务端渲染与同构实践

    • IM聊天系统前端开发实践

    • 微前端开发实战

    • React进阶实践

  • Vue专栏

  • 移动端专栏

  • Node专栏

  • 前端工程化专栏

  • 算法专栏

  • Typescript专栏

  • 其他专栏

完整面试题地址:
作者:程序员poetry
扫码关注作者公众号:「前端进阶之旅」 每天分享技术干货
前端进阶之旅公众号二维码

# 题目

把只包含质因子2、3和5的数称作丑数(Ugly Number)。

例如6、8都是丑数,但14不是,因为它包含质因子7。

习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

# 思路

丑数只能被2、3、5整除,说明第n个丑数只能是0 - n-1中某个丑数✖️2、✖️3、✖️5的结果。

而且,这个数即第0 - n-1个丑数✖️2、✖️3、✖️5的结果中比第n-1个丑数大的最小值。

按照上面的规律,我们可以依次求出第0 - n个丑数。

简单做法:

  • 1.每次把第0 - n-1个丑数✖️(2、3、5)
  • 2.分别找到第0 - n-1个丑数✖️2、✖️3、✖️5的结果中比第n-1个丑数大的最小值。
  • 3.比较三个数取最小值加入到丑数队列中

优化:

  • 1.前面的数不必每个都乘
  • 2.记录下✖️(2、3、5)后刚好比当前最大丑数大的这三个值的下标 i2,i3,i5
  • 3.下次比较从这 i2,i3,i5 三个下标开始乘起
  • 4.最后取arr[i2]✖️2、arr[i3]✖️3、arr[i5]✖️5 的最小值

丑数

# 代码

    function GetUglyNumber_Solution(index) {
      if (index <= 0) {
        return 0;
      }
      let arr = [1];
      let i2 = i3 = i5 = 0;
      let cur = 0;
      while (arr.length < index) {
        arr.push(Math.min(arr[i2] * 2, arr[i3] * 3, arr[i5] * 5));
        const current = arr[arr.length - 1];
        while (arr[i2] * 2 <= current) {
          i2++;
        }
        while (arr[i3] * 3 <= current) {
          i3++;
        }
        while (arr[i5] * 5 <= current) {
          i5++;
        }
      }
      return arr[index - 1];
    }
@前端进阶之旅: 代码已经复制到剪贴板
fe
基础篇
进阶篇
高频篇
精选篇
手写篇
原理篇
面经篇
AI 面试
自检篇
每日一题
  • 综合
    • 综合题型
    • 其他问题
    • 设计模式
    • 思维导图
    • 学习路线
  • 前端基础
    • HTTP
    • 浏览器
    • 计算机基础
  • 进阶学习
    • NPM工作流
    • Docker
    • Canvas
    • Node学习指南
    • 前端综合文章
  • 其他
    • Handbook
    • 职场话题
    • CSS可视化
小程序题库
公众号动态
博客动态
开发者导航
  • React专栏

    • React组合式开发实战

      • 前端开发的四个时代
      • 企业管理系统的前世今生
      • 可视化页面搭建工具
      • 实战篇 01:开发前准备
      • 实战篇 02:项目脚手架
      • 实战篇 03:页面布局方案
      • 实战篇 04:权限管理机制
      • 实战篇 05:菜单匹配逻辑
      • 实战篇 06:消息通知设计
      • 实战篇 07:多语言支持
      • 继往开来:可视化页面搭建工具
    • React Hooks与Immutable实战

    • React SSR服务端渲染与同构实践

    • IM聊天系统前端开发实践

    • 微前端开发实战

    • React进阶实践

  • Vue专栏

  • 移动端专栏

  • Node专栏

  • 前端工程化专栏

  • 算法专栏

  • Typescript专栏

  • 其他专栏