[[440250]]

本文轉載自微信公眾號「程序員千羽」，作者程序員千羽。轉載本文請聯系程序員千羽公眾號。

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]; 
    } 
 
} 

參考鏈接：https://leetcode-cn.com/problems/chou-shu-lcof/solution/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t/