leetcode [264]Ugly Number II

ゝ一纸荒年。 2021-12-07 14:21 106阅读 0赞

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.  `1` is typically treated as an ugly number.
2.  `n` does not exceed 1690.

**题目大意：**

寻找第n个丑数，n不超过1690。

**解法：**

将找到的丑数记录在一个数组中，返回第n个丑数，后面的丑数一定是前面的丑数生成的，一定是前面某个丑数×2、前面某个丑数×3、前面某个丑数×5这三个数中的一个最小值，使用index2，index3，index5的需要×2，×3，×5下标的数字，将生成的丑数继续加到数组中。

java:

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

转载于:https://www.cnblogs.com/xiaobaituyun/p/10842530.html

发表评论取消回复

表情：

评论列表（有 0 条评论，106人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Medium - 264. Ugly Number II

Topic Math Dynamic Programming Heap Description [https://leetcode.com/pr

梦里梦外;/ 2023年01月10日 01:18/ 0 赞/ 93 阅读

相关 LeetCode 263. Ugly Number

今天觉得无聊，就做了几道LeeCode上面的题，碰到了一道关于Ugly Number的题目，其实这道题蛮简单的，但是第一次做的时候，想的比较简单，碰到了钉子，题目的大意如下：

快来打我*/ 2022年09月25日 03:22/ 0 赞/ 112 阅读

相关 264 Ugly Number II

除第一个数 1 外，所有的Ugly Number都是有较小的Ugly Number乘2，3，5得到的，所以本题的关键就是在 1\2，2\2，3\2，4\2，5\2，6\

客官°小女子只卖身不卖艺/ 2022年08月04日 09:12/ 0 赞/ 35 阅读

相关 leetcode 264. Ugly Number II

Write a program to find the `n`\-th ugly number. Ugly numbers are positive numbers whos

超、凢脫俗/ 2022年07月26日 00:15/ 0 赞/ 109 阅读

相关 [leetcode]: 263. Ugly Number

1.题目 Write a program to check whether a given number is an ugly number. Ugly numbers

落日映苍穹つ/ 2022年06月15日 02:40/ 0 赞/ 111 阅读

相关 264.Ugly Number II

/\ Write a program to find the n-th ugly number. Ugly numbers are positive numbe

比眉伴天荒/ 2022年06月09日 03:55/ 0 赞/ 97 阅读

相关 leetcode 264. Ugly Number II 计算第K个丑数

Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose p

末蓝、/ 2022年06月08日 13:24/ 0 赞/ 93 阅读

相关 4. Ugly Number II

4. Ugly Number II Description Ugly number is a number that only have factors 2

╰+哭是因爲堅強的太久メ/ 2022年05月27日 07:29/ 0 赞/ 96 阅读

相关【Leetcode】264. Ugly Number II（DP）（规律）

Write a program to find the `n`\-th ugly number. Ugly numbers are positive numberswhose

迷南。/ 2022年01月16日 01:41/ 0 赞/ 121 阅读

相关 leetcode [264]Ugly Number II

Write a program to find the `n`\-th ugly number. Ugly numbers are positive numbers whos

ゝ一纸荒年。/ 2021年12月07日 14:21/ 0 赞/ 107 阅读