美文网首页
264. 丑数 II

264. 丑数 II

作者: calm_peng | 来源:发表于2018-11-06 21:01 被阅读0次

编写一个程序,找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:

1 是丑数。
n 不超过1690。


image.png
分析:除了第一个丑数1以外 每一个丑数都是 由 2,3,5,
 乘以原有的丑数集合{1。。。。},来扩充,
注意一点,在该题目中每次扩充一位即可,
每次都要比较,(2,3,5)所乘得到的数,
选择最小的数
(,加入丑数集合中,此时,将刚刚被乘以的那个(
2,3,5)去乘以,集合中的下一个数
(可能会相等,此时那相等的数,同时乘以集合的下一个)。



(2,3,5)每个都数都要乘以丑数数组中的每一个数,
设每个(2,3,5)都有一个指针(都在遍历丑数数组),
当乘以丑数数组的积为最小时
(若相等,指针都会指向下一个),
指针指向下一个,依次类推。

*/
class Solution {
    public int nthUglyNumber(int n) {
        
        
        int [] res = new int[n];
       res[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0,k = 0;
        for( k = 1;k<n;k++) {
            int m2 = res[i2] * 2, m3 = res[i3] * 3, m5 = res[i5] * 5;
            int mn = Math.min(m2, Math.min(m3, m5));
            if (mn == m2) ++i2;
            if (mn == m3) ++i3;
            if (mn == m5) ++i5;
            res[k] = mn;
        }
        return res[k-1];
        
        
    }
}

leetcode 原题

相关文章

  • 264. 丑数 II

    编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 输入: n = 10...

  • 264.丑数II

    题目描述 编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 思路 1....

  • 264. 丑数 II

    编写一个程序,找出第 n 个丑数。 丑数就是质因数只包含 2, 3, 5 的正整数。 示例: 输入: n = 10...

  • Leetcode 264. 丑数 II

    题目描述 编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例 1: 输入:...

  • 264. Ugly Number II 丑数 ||

    题目链接tag: Medium; question:  Write a program to find the n...

  • 2019-02-04

    LeetCode 264. Ugly Number II Description Write a program ...

  • 丑数II

    题目描述 设计一个算法,找出只含素因子2,3,5 的第 n 大的数。1也是一个丑数。 思路 方法一每个丑数都是2....

  • 丑数 II

    设计一个算法,找出只含素因子2,3,5 的第 n 小的数。 符合条件的数如:1, 2, 3, 4, 5, 6, 8...

  • 丑数 II

    编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 输入: n = 10...

  • Leetcode-Java(二十七)

    263. Ugly Number 264. Ugly Number II 分析:这道题最直观地想法是暴力查找,但不...

网友评论

      本文标题:264. 丑数 II

      本文链接:https://www.haomeiwen.com/subject/omjpxqtx.html