文档章节

LeetCode:Super Ugly Number - 超级丑数

北风其凉
 北风其凉
发布于 2015/12/19 11:24
字数 455
阅读 3064
收藏 0

1、题目名称

Super Ugly Number(超级丑数)

2、题目地址

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

3、题目内容

英文:

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list    primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes    = [2, 7, 13, 19] of size 4.

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

说明:超级丑数具有如下特征:1是超级丑数,超级丑数可以表示为有限个指定质数的乘积

注意:

1)丑数的定义是:1是丑数,丑数可以表示为有限个2、3、5的乘积,超级丑数是对丑数概念的一个扩展

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

3)关于“找到第n个丑数”,请参考 Ugly Number II(LeetCode #264)

5、解题方法

找出第n个超级丑数,思路与找出第n个丑数是一样的。区别仅在与找出第n个丑数时,用三个数字记录中间变量,而在找第n个超级丑数时,用一个数组记录。

Java代码如下:

/**
 * 功能说明:LeetCode 313 - Super Ugly Number 
 * 开发人员:Tsybius2014 
 * 开发时间:2015年12月19日
 */
public class Solution {

    /**
     * 求第N个超级丑数
     * @param n
     * @param primes 
     * @return 第N个超级丑数
     */
    public int nthSuperUglyNumber(int n, int[] primes) {
        
        int[] superUglyNumbers = new int[n];
        superUglyNumbers[0] = 1;
        int[] idxPrimes = new int[primes.length];
        for (int i = 0; i < idxPrimes.length; i++) {
            idxPrimes[i] = 0;
        }
        
        int counter = 1;
        while (counter < n) {
            
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < primes.length; i++) {
                int temp = superUglyNumbers[idxPrimes[i]] * primes[i];
                min = min < temp ? min : temp;
            }

            for (int i = 0; i < primes.length; i++) {
                if (min == superUglyNumbers[idxPrimes[i]] * primes[i]) {
                    idxPrimes[i]++;
                }
            }
            
            superUglyNumbers[counter] = min;
            counter++;
        }
        
        return superUglyNumbers[n - 1];
    }
}

END

© 著作权归作者所有

共有 人打赏支持
北风其凉

北风其凉

粉丝 118
博文 498
码字总数 463468
作品 4
朝阳
程序员
私信 提问
加载中

评论(2)

北风其凉
北风其凉

引用来自“Vek_lip”的评论

初始化时是不是idxPrimes[i] = 应该为1而不是0?
这是可以AC的代码,你可以把代码跑一遍。
Vek_lip
Vek_lip
初始化时是不是idxPrimes[i] = 应该为1而不是0?
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
0
1
LeetCode:Ugly Number II - 丑数2:找出第n个丑数

1、题目名称 Ugly Number II(丑数2:找出第n个丑数) 2、题目地址 https://leetcode.com/problems/ugly-number-ii/ 3、题目内容 英文:Write a program to find the -th ugly number. 中文:...

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

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

Triangle23
2013/05/05
0
0
Leetcode 313. Super Ugly Number

版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn.net/Quincuntial/article/details/82117516 文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Descr...

SnailTyan
2018/08/27
0
0
Ugly Number(leetcode263)

Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers whose prime factors only include . Example 1: Input: 6Output: trueExplanatio......

woshixin
2018/12/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

4.57 MariaDB慢查询日志 4.58 Tomcat_JDK部署 4.59 zrlog安装 4.60 Nginx代理Tomcat

4.57 MariaDB慢查询日志 为什么要配置慢查询日志? 目的是为了帮助我们分析MariaDB的瓶颈点。 如何配置? 1)进入MariaDB里面执行:show variables like 'slow%';show variables li...

Champin
今天
3
0
自动机器学习简述(AutoML)

为什么需要自动机器学习 对于机器学习的新用户而言,使用机器学习算法的一个主要的障碍就是算法的性能受许多的设计决策影响。随着深度学习的流行,工程师需要选择相应的神经网络架构,训练过...

naughty
今天
2
0
Android Studio Unable to resolve dependency for错误的排查

记录一次Android Studio Unable to resolve dependency for错误的排查 Android Studio 3.2.1 错误提示 Unable to resolve dependency for... 原因:在gradle中设置的代理并没有gradle 4.6的版......

Gemini-Lin
今天
0
0
java常用设计模式

设计模式; 一个程序员对设计模式的理解: “不懂”为什么要把很简单的东西搞得那么复杂。后来随着软件开发经验的增加才开始明白我所看到的“复杂”恰恰就是设计模式的精髓所在,我所理解的“...

呵呵哒灬
今天
5
0
Kafka入门

1、Kafka使用背景 在我们大量使用分布式数据库、分布式计算集群的时候,是否会遇到这样的一些问题: 我们想分析下用户行为(pageviews),以便我们设计出更好的广告位 我想对用户的搜索关键词...

watermelon11
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部