【LeetCode】丑数 IIJava 题解

HQ数字卡

关注

发布于: 2021 年 04 月 11 日

题目

给你一个整数 n ，请你找出并返回第 n 个丑数。

丑数就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：

输入：n = 10 输出：12 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

提示：

1 <= n <= 1690

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/ugly-number-ii

代码

public class DayCode {    public static void main(String[] args) {        int num = 6;        int ans = new DayCode().nthUglyNumber(num);        System.out.println("ans is " + ans);    }
    /**     * 时间复杂度 O(n)     * 空间复杂度 O(1)     * @param n     * @return     */    public int nthUglyNumber(int n) {        int size = 1690;        int[] nums = new int[size];        nums[0] = 1;        int ugly = 0, i2 = 0, i3 = 0, i5 = 0;        for (int i = 1; i < size; i++ ) {            ugly = Math.min(Math.min(nums[i2] * 2, nums[i3] * 3), nums[i5] * 5);            nums[i] = ugly;            if (ugly == nums[i2] * 2) {                i2++;            }            if (ugly == nums[i3] * 3) {                i3++;            }            if (ugly == nums[i5] * 5) {                i5++;            }        }
        return nums[n-1];    }}

复制代码

总结

今天的每日一题，和昨天的丑数形成呼应，比昨天的复杂一点，实践五毒神掌！这里的 n = 1690 条件很重要，我们可以直接用来初始化数组。
坚持每日一题，加油！

发布于: 2021 年 04 月 11 日阅读数: 12

原文链接:【http://xie.infoq.cn/article/8dcdaba27c8b95f937b00a9d8】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】丑数 IIJava 题解

题目

代码

总结

HQ数字卡

评论