264. Ugly Number II

栏目: Java · 发布时间: 6年前

内容简介:Write a program to find the n-th ugly number.Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.Example:

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

1 is typically treated as an ugly number.

n does not exceed 1690.

难度:medium

题目:写程序找出第n个丑数。丑数公因子只由2,3,5构正的正整数。

思路:三路指针。

Runtime: 2 ms, faster than 99.79% of Java online submissions for Ugly Number II.

Memory Usage: 36.8 MB, less than 32.39% of Java online submissions for Ugly Number II.

class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n; i++) {
            ugly[i] = Math.min(ugly[p2] * 2, Math.min(ugly[p3] * 3, ugly[p5] * 5));
            if (ugly[i] == ugly[p2] * 2) {
                p2++;
            }
            if (ugly[i] == ugly[p3] * 3) {
                p3++;
            }
            if (ugly[i] == ugly[p5] * 5) {
                p5++;
            }
        }
        
        return ugly[n - 1];
    }
}

以上所述就是小编给大家介绍的《264. Ugly Number II》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Beginning XML with DOM and Ajax

Beginning XML with DOM and Ajax

Sas Jacobs / Apress / 2006-06-05 / USD 39.99

Don't waste time on 1,000-page tomes full of syntax; this book is all you need to get ahead in XML development. Renowned web developer Sas Jacobs presents an essential guide to XML. Beginning XML with......一起来看看 《Beginning XML with DOM and Ajax》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具