264. Ugly Number II

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];
    }
}

原文 

https://segmentfault.com/a/1190000018344160

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 264. Ugly Number II

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址