您现在的位置是：亿华云 > IT科技

让我们一起学学丑数，你会了吗？

亿华云2025-10-02 08:57:51【IT科技】7人已围观

简介本文转载自微信公众号「程序员千羽」，作者程序员千羽。转载本文请联系程序员千羽公众号。Leetcode : https://leetcode-cn.com/problems/chou-shu-lcof/

本文转载自微信公众号「程序员千羽」，让们作者程序员千羽。起学转载本文请联系程序员千羽公众号。学丑

Leetcode : https://leetcode-cn.com/problems/chou-shu-lcof/

“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_36_nthUglyNumber/Solution.java

丑数

“题目描述：我们把只包含质因子 2、让们3 和 5 的起学数称作丑数(Ugly Number)。求按从小到大的学丑顺序的第 n 个丑数。难度：中等

示例：

输入: n = 10 输出: 12 解释: 1,让们 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。香港云服务器

思路：

“丑数的起学递推性质:丑数只包含因子2,3,5，因此有“丑数=某较小丑数x洇子”(例如: 10=5x2)。学丑

因此，让们可设置指针a,起学 b,c指向首个丑数(即1 )，循环根据递推公式得到下个丑数,学丑并每轮将对应指针执行 +1即可。

复杂度分析:

时间复杂度O(N) ：中N=n，让们动态规划需遍历计算dp列表。起学空间复杂度O(N) ：长度为N的学丑dp列表使用0(N)的服务器托管额外空间。 package com.nateshao.sword_offer.topic_36_nthUglyNumber; /** * @date Created by 邵桐杰 on 2021/12/11 22:54 * @微信公众号程序员千羽 * @个人网站 www.nateshao.cn * @博客 https://nateshao.gitee.io * @GitHub https://github.com/nateshao * @Gitee https://gitee.com/nateshao * Description: 丑数 * 描述：我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。 */ public class Solution { public static void main(String[] args) { System.out.println("nthUglyNumber(10) = " + nthUglyNumber(10));//nthUglyNumber(10) = 12 System.out.println("nthUglyNumber2(10) = " + nthUglyNumber2(10));//nthUglyNumber2(10) = 12 } /** * 思路：乘 2 或 3 或 5，之后比较取最小值。 * * @param n * @return */ public static int nthUglyNumber(int n) { if (n <= 0) return 0; int[] arr = new int[n]; arr[0] = 1;// 第一个丑数为 1 int multiply2 = 0, multiply3 = 0, multiply5 = 0; for (int i = 1; i < n; i++) { int min = Math.min(arr[multiply2] * 2, Math.min(arr[multiply3] * 3, arr[multiply5] * 5)); arr[i] = min; if (arr[multiply2] * 2 == min) multiply2++; if (arr[multiply3] * 3 == min) multiply3++; if (arr[multiply5] * 5 == min) multiply5++; } return arr[n - 1];// 返回第 n 个丑数 } /** * 作者：Krahets * * @param n * @return */ public static int nthUglyNumber2(int n) { int a = 0, b = 0, c = 0; int[] dp = new int[n]; dp[0] = 1; for (int i = 1; i < n; i++) { int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5; dp[i] = Math.min(Math.min(n2, n3), n5); if (dp[i] == n2) a++; if (dp[i] == n3) b++; if (dp[i] == n5) c++; } return dp[n - 1]; } }