[[440250]]

本文轉(zhuǎn)載自微信公眾號(hào)「程序員千羽」，作者程序員千羽。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員千羽公眾號(hào)。

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

丑數(shù)

“題目描述 ：我們把只包含質(zhì)因子 2、3 和 5 的數(shù)稱作丑數(shù)(Ugly Number)。求按從小到大的順序的第 n 個(gè)丑數(shù)。難度：中等

示例 ：

輸入: n = 10 
輸出: 12 
解釋: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個(gè)丑數(shù)。 

思路：

“丑數(shù)的遞推性質(zhì):丑數(shù)只包含因子2,3,5， 因此有“丑數(shù)=某較小丑數(shù)x洇子”(例如: 10=5x2)。

因此，可設(shè)置指針a, b,c指向首個(gè)丑數(shù)(即1 )，循環(huán)根據(jù)遞推公式得到下個(gè)丑數(shù), 并每輪將對(duì)應(yīng)指針執(zhí)行 +1即可。

復(fù)雜度分析:

• 時(shí)間復(fù)雜度O(N) ：中N=n，動(dòng)態(tài)規(guī)劃需遍歷計(jì)算dp列表。
• 空間復(fù)雜度O(N) ：長(zhǎng)度為N的dp列表使用0(N)的額外空間。

package com.nateshao.sword_offer.topic_36_nthUglyNumber; 
 
/** 
 * @date Created by 邵桐杰 on 2021/12/11 22:54 
 * @微信公眾號(hào) 程序員千羽 
 * @個(gè)人網(wǎng)站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description: 丑數(shù) 
 * 描述：我們把只包含質(zhì)因子 2、3 和 5 的數(shù)稱作丑數(shù)（Ugly Number）。求按從小到大的順序的第 n 個(gè)丑數(shù)。 
 */ 
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;// 第一個(gè)丑數(shù)為 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 個(gè)丑數(shù) 
    } 
 
    /** 
     * 作者：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/