文档章节

LeetCode:Ugly Number II - 丑数2:找出第n个丑数

北风其凉
 北风其凉
发布于 2015/08/23 13:29
字数 1387
阅读 6666
收藏 1

1、题目名称

Ugly Number II(丑数2:找出第n个丑数)

2、题目地址

https://leetcode.com/problems/ugly-number-ii/

3、题目内容

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

中文:写程序找出第n个丑数

说明:丑数具有如下特征:1是丑数,丑数可以表示为有限个2、3、5的乘积

注意:关于“判断指定数字是否为丑数”,请参考Ugly Number(LeetCode #263)

5、一个TLE的方法

一个最容易想到的方法,就是从1开始依次向后判断各自然数是否为丑数,一直判断到第n个丑数,返回第n个丑数的值。这种方法由于充斥了大量的重复计算,效率很低,因此会导致TLE(Time Limit Exceeded)的结果。

Java代码如下:

/**
 * 功能说明:LeetCode 263 - Ugly Number
 * 开发人员:Tsybius2014
 * 开发时间:2015年8月23日
 */
public class Solution {
    
    /**
     * 求第N个丑数
     * @param n
     * @return 第N个丑数
     */
    public int nthUglyNumber(int n) {
    
        if (n <= 1) {
            return 1;
        }

        int counter = 0;
        for (int i = 1; ; i++) {
            
            if (isUgly(i)) {
                counter++;
                if (counter == n) {
                    return i;
                }
            } 
        }
    }
    
    /**
     * 判断数字是否为丑数
     * @param num 被判断数字
     * @return true:丑数,false:非丑数
     */
    public boolean isUgly(int num) {
        
        if (num <= 0) {
            return false;
        }
        
        while (num % 2 == 0) num /= 2;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        
        if (num == 1) {
            return true;
        } else {
            return false;
        }
    }
}

6、解题方法

关于如果更加快速有效地找出第n个丑数的问题,网上已经有很多解题方法和大牛的博客可以参考,这里只是简要说明我用的方法:

  1. 申请一个长度为n的数组uglyNumbers,用于从小到大顺序存储n个丑数,数组中的首项为1,即第一个丑数为1

  2. 设置三个变量idx2、idx3、idx5存储下标,初始值都为0

  3. 找出数组uglyNumbers[idx2]*2、uglyNumbers[idx3]*3、uglyNumbers[idx5]*5的最小值,最小值即为下一个丑数,同时更新最小值对应的下标,如果多个数字同时为最小值,则它们的下标都要更新

  4. 找到第n个丑数时,循环结束

一段实现此方法的Java代码如下:

/**
 * 功能说明:LeetCode 264 - Ugly Number II
 * 开发人员:Tsybius2014
 * 开发时间:2015年8月23日
 */
public class Solution {
    
    /**
     * 求第N个丑数
     * @param n
     * @return 第N个丑数
     */
    public int nthUglyNumber(int n) {
        
        int[] uglyNumbers = new int[n];
        uglyNumbers[0] = 1;
//      System.out.println("uglyNumbers[0]:1");
        
        int idx2 = 0;
        int idx3 = 0;
        int idx5 = 0;

        int counter = 1;
        while (counter < n) {

//          System.out.println("-----------");
//          System.out.println("idx2:" + idx2 + ";ugly[idx2]:" + uglyNumbers[idx2]);
//          System.out.println("idx3:" + idx3 + ";ugly[idx3]:" + uglyNumbers[idx3]);
//          System.out.println("idx5:" + idx5 + ";ugly[idx5]:" + uglyNumbers[idx5]);
//          System.out.println("idx2:" + idx2 + ";idx3:" + idx3 + ";idx5:" + idx5);
            
            int min = minOf(
                uglyNumbers[idx2] * 2, 
                uglyNumbers[idx3] * 3, 
                uglyNumbers[idx5] * 5);
            
            if (min == uglyNumbers[idx2] * 2) {
//              System.out.println("min==ugly[idx2]*2:" + uglyNumbers[idx2] * 2);
//              System.out.println("idx2:" + idx2 + "→" + (idx2 + 1));
                idx2++;
            }

            if (min == uglyNumbers[idx3] * 3) {
//              System.out.println("min==ugly[idx3]*3:" + uglyNumbers[idx3] * 3);
//              System.out.println("idx3:" + idx3 + "→" + (idx3 + 1));
                idx3++;
            }

            if (min == uglyNumbers[idx5] * 5) {
//              System.out.println("min==ugly[idx5]*5:" + uglyNumbers[idx5] * 5);
//              System.out.println("idx5:" + idx5 + "→" + (idx5 + 1));
                idx5++;
            }
            
            uglyNumbers[counter] = min;
//          System.out.println("uglyNumbers[" + counter + "]:" + min);
            counter++;
        }

//      System.out.println("-----------");
//      System.out.println("return:" + uglyNumbers[n - 1]);
        
        return uglyNumbers[n - 1];
    }
    
    /**
     * 求三个数字中最小的数字
     * @param a 数字a
     * @param b 数字b
     * @param c 数字c
     * @return a、b、c中最小的数字
     */
    private int minOf(int a, int b, int c) {
        int temp = a < b ? a : b;
        return temp < c ? temp : c; 
    }
}

为了方便理解这段代码,我在这段代码里加入了System.out.println函数用于将结果输出到控制台。解除这些注释行,并指定输入的n为15,执行函数时输出到控制台的结果如下:

uglyNumbers[0]:1
-----------
idx2:0;ugly[idx2]:1
idx3:0;ugly[idx3]:1
idx5:0;ugly[idx5]:1
idx2:0;idx3:0;idx5:0
min==ugly[idx2]*2:2
idx2:0→1
uglyNumbers[1]:2
-----------
idx2:1;ugly[idx2]:2
idx3:0;ugly[idx3]:1
idx5:0;ugly[idx5]:1
idx2:1;idx3:0;idx5:0
min==ugly[idx3]*3:3
idx3:0→1
uglyNumbers[2]:3
-----------
idx2:1;ugly[idx2]:2
idx3:1;ugly[idx3]:2
idx5:0;ugly[idx5]:1
idx2:1;idx3:1;idx5:0
min==ugly[idx2]*2:4
idx2:1→2
uglyNumbers[3]:4
-----------
idx2:2;ugly[idx2]:3
idx3:1;ugly[idx3]:2
idx5:0;ugly[idx5]:1
idx2:2;idx3:1;idx5:0
min==ugly[idx5]*5:5
idx5:0→1
uglyNumbers[4]:5
-----------
idx2:2;ugly[idx2]:3
idx3:1;ugly[idx3]:2
idx5:1;ugly[idx5]:2
idx2:2;idx3:1;idx5:1
min==ugly[idx2]*2:6
idx2:2→3
min==ugly[idx3]*3:6
idx3:1→2
uglyNumbers[5]:6
-----------
idx2:3;ugly[idx2]:4
idx3:2;ugly[idx3]:3
idx5:1;ugly[idx5]:2
idx2:3;idx3:2;idx5:1
min==ugly[idx2]*2:8
idx2:3→4
uglyNumbers[6]:8
-----------
idx2:4;ugly[idx2]:5
idx3:2;ugly[idx3]:3
idx5:1;ugly[idx5]:2
idx2:4;idx3:2;idx5:1
min==ugly[idx3]*3:9
idx3:2→3
uglyNumbers[7]:9
-----------
idx2:4;ugly[idx2]:5
idx3:3;ugly[idx3]:4
idx5:1;ugly[idx5]:2
idx2:4;idx3:3;idx5:1
min==ugly[idx2]*2:10
idx2:4→5
min==ugly[idx5]*5:10
idx5:1→2
uglyNumbers[8]:10
-----------
idx2:5;ugly[idx2]:6
idx3:3;ugly[idx3]:4
idx5:2;ugly[idx5]:3
idx2:5;idx3:3;idx5:2
min==ugly[idx2]*2:12
idx2:5→6
min==ugly[idx3]*3:12
idx3:3→4
uglyNumbers[9]:12
-----------
idx2:6;ugly[idx2]:8
idx3:4;ugly[idx3]:5
idx5:2;ugly[idx5]:3
idx2:6;idx3:4;idx5:2
min==ugly[idx3]*3:15
idx3:4→5
min==ugly[idx5]*5:15
idx5:2→3
uglyNumbers[10]:15
-----------
idx2:6;ugly[idx2]:8
idx3:5;ugly[idx3]:6
idx5:3;ugly[idx5]:4
idx2:6;idx3:5;idx5:3
min==ugly[idx2]*2:16
idx2:6→7
uglyNumbers[11]:16
-----------
idx2:7;ugly[idx2]:9
idx3:5;ugly[idx3]:6
idx5:3;ugly[idx5]:4
idx2:7;idx3:5;idx5:3
min==ugly[idx2]*2:18
idx2:7→8
min==ugly[idx3]*3:18
idx3:5→6
uglyNumbers[12]:18
-----------
idx2:8;ugly[idx2]:10
idx3:6;ugly[idx3]:8
idx5:3;ugly[idx5]:4
idx2:8;idx3:6;idx5:3
min==ugly[idx2]*2:20
idx2:8→9
min==ugly[idx5]*5:20
idx5:3→4
uglyNumbers[13]:20
-----------
idx2:9;ugly[idx2]:12
idx3:6;ugly[idx3]:8
idx5:4;ugly[idx5]:5
idx2:9;idx3:6;idx5:4
min==ugly[idx2]*2:24
idx2:9→10
min==ugly[idx3]*3:24
idx3:6→7
uglyNumbers[14]:24
-----------
return:24

END

© 著作权归作者所有

北风其凉

北风其凉

粉丝 120
博文 497
码字总数 462305
作品 4
朝阳
程序员
私信 提问
加载中

评论(3)

congyh
congyh
赞, 加了输出后过程更容易看懂了. 感谢分享~
杨森森
大赞,这个算法很好,比leetcode提示的算法好很多,谢谢分享
d
dOck颖
0
LeetCode:Super Ugly Number - 超级丑数

1、题目名称 Super Ugly Number(超级丑数) 2、题目地址 https://leetcode.com/problems/super-ugly-number/ 3、题目内容 英文: Write a program to find the nth super ugly number. Sup......

北风其凉
2015/12/19
3.3K
2
LeetCode:Ugly Number - 丑数1:判断指定数字是否为丑数

1、题目名称 Ugly Number(丑数1:判断指定数字是否为丑数) 2、题目地址 https://leetcode.com/problems/ugly-number 3、题目内容 英文:Write a program to check whether a given number...

北风其凉
2015/08/23
4.1K
1
寻找丑数及关于程序优化效率的一点说明

一、问题描述 如果一个整数值含有因数2,3,5(包括1和该整数本身)的整数称为丑数(Ugly Number)。换句话说丑数ugly_number是可以表示成形如下面表达式的形式,表达式中的i,j,k均是大于等于0的...

Triangle23
2013/05/05
336
0
编程题——31~40

三十一、连续子数组的最大和 输入一个整数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 三十二、从1到n整数中...

thanatos_y
2016/07/26
18
0
Humble Numbers(丑数) 超详解!

给定一个素数集合 S = { p[1],p[2],...,p[k] },大于 1 且素因子都属于 S 的数我们成为丑数(Humble Numbers or Ugly Numbers),记第 n 大的丑数为 h[n]。 算法 1:   一种最容易想到的方...

angel_kitty
2017/02/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

PhotoShop 色调:理解直方图/RGB通道信息

一、直方图:图表的形式,展示图像像素分布的情况 1.平均值:表示平均亮度 2.标准偏差值:表示亮度值范围内的中间值 3.像素: 表示用于计算直方图的像素总数 4.色阶:显示指针下面的区域亮度...

东方墨天
7分钟前
2
0
wildfly(JBoss AS)应用服务器快速入门

什么是wildfly JBoss AS 从8版本起名为wildfly。Wildfly是一个开源的基于JavaEE的轻量级应用服务器。可以在任何商业应用中免费使用。 WildFly是一个灵活的、轻量的、强大管理能力的应用程序服...

程序新视界
32分钟前
2
0
Java集合类常见面试知识点总结

Java集合类学习总结 这篇总结是基于之前博客内容的一个整理和回顾。 这里先简单地总结一下,更多详细内容请参考我的专栏:深入浅出Java核心技术 https://blog.csdn.net/column/details/21930...

Java技术江湖
35分钟前
6
0
怎么用for循环打出爱心

先上效果图: 这是用*组成的爱心,下面讲讲思路: 首先这个图形可以拆分成三部分:第一部分是上面三行的两个梯形,第二部分是中间三行的长方形,第三部分是最下面的倒三角形。 其实图形拆分好...

INEVITABLE
41分钟前
4
0
用HttpUrlConnection伪造成HttpClient

https://www.jianshu.com/p/27ad06cc39d2

shzwork
46分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部