栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

剑指offer 62. 丑数-java

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

剑指offer 62. 丑数-java

AcWing 62. 丑数

多路归并

原题链接

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

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

求第 n 个丑数的值。

数据范围
1≤n≤1000

代码案例:输入:5
输出:5

注意:习惯上我们把 1 当做第一个丑数

题解

三指针的思想,所以定义3个指针i, j, k。
vector存储的是丑数数组,一开始只有1个1,后面 动态添加元素进vector。
t取出的是3个指针分别指向的3个子数组(2 3 5)中的最小值。如果最小值是3个子数组中的哪一个,就把里面的指针i j k 增1。因为可能同时出现在多个数组,所以用3个if来表示。
最后输出vector的最后一位,就是第n个丑数。
或者可以这样理解:
我们已经明确了 一个非1的丑数 如果能够除以2 3 或者5 就能得到一个比它小的丑数,比如 6可以除以3 得到2,6除以2得到3. 30可以得到 2 3 5 6 15 10等丑数

所有的丑数 都可以从比他大的某个丑数通过这种方式计算得到,也就达到了不重不漏中的不漏。

我们剩下的问题就是避免不重复而有序的生成这些丑数

这里设置三个队列 专门有序存放当前答案集合中存放的丑数的2 3 5的倍数

每次从三个队列中取出最小的数放入答案集合,并且将这个数乘以2 3 5放入相应的队列

那么答案集合中的丑数是有序的,三个队列中的丑数也是有序的

class Solution {
    public int getUglyNumber(int n) {
        int i = 0 , j=0 , k=0;
        ArrayList a = new ArrayList<>();
        a.add(1);
        while(--n > 0){
            int t = Math.min(Math.min(a.get(i)*2,a.get(j)*3), a.get(k)*5);
             a.add(t);
             if(a.get(i)*2 == t) i++;
             if(a.get(j)*3== t) j++;
             if(a.get(k)*5 == t) k++;
        }
         int b = a.size()-1;
        return a.get(b);
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/973920.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号