4. Ugly Number II

╰+哭是因爲堅強的太久メ 2022-05-27 07:29 147阅读 0赞

# 4. Ugly Number II #

### Description ###

Ugly number is a number that only have factors 2, 3 and 5.
    Design an algorithm to find the nth ugly number. The first 10 ugly 
    numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

### Example ###

If n=9, return 10.

### Solution ###

import java.util.*;
    public class Solution {
        /** * @param n: An integer * @return: the nth prime number as description. */
        public int nthUglyNumber(int n) {
            // write your code here
            ArrayList<Integer> list = new ArrayList<>();
            list.add(1);
            int i=1;
            //使用三个计数值，分别表示2,3,5的倍数的最小值的当前下标
            int min = 1,m2 = 0,m3 = 0,m5 = 0;
            while(i<=n){
                i++;
                min = Math.min(Math.min(list.get(m2)*2,list.get(m3)*3),list.get(m5)*5);
                list.add(min);
                if(min == list.get(m2)*2) m2++;
                else if(min == list.get(m3)*3) m3++;
                else m5++;
                //这里注意可能有重复值，需要去重
                while(list.get(m2)*2<=min) m2++;
                while(list.get(m3)*3<=min) m3++;
                while(list.get(m5)*5<=min) m5++;
            }
            return list.get(n-1);
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode - Medium - 264. Ugly Number II

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

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

相关 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 赞/ 75 阅读

相关 263 Ugly Number

public boolean isUgly(int num) { if (num == 0)//不要忘记num=0的情况

深碍√TFBOYSˉ_/ 2022年08月04日 08:44/ 0 赞/ 143 阅读

相关 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 赞/ 156 阅读

相关 263. Ugly Number

Write a program to check whether a given number is an ugly number. Ugly numbers are pos

短命女/ 2022年07月15日 01:28/ 0 赞/ 167 阅读

相关 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 赞/ 141 阅读

相关 263.Ugly Number

/ Write a program to check whether a given number is an ugly number. U

- 日理万妓/ 2022年06月09日 03:54/ 0 赞/ 156 阅读

相关 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 赞/ 148 阅读

相关【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 赞/ 166 阅读

相关 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 赞/ 162 阅读