?

1 題目描述

2 解題方法

方法1：最小堆儲存數組

同時設置一個集合存放我們已經考慮過的數，每看到一個丑數n，把2n，3n，5n放入這個最小堆。

class Solution:def nthUglyNumber(self, n: int) -> int:lst=[1]ret=-1s={1}heapq.heapify(lst)while(n!=0):ret=heapq.heappop(lst)n=n-1if(2*ret not in s):s.add(2*ret)heapq.heappush(lst,2*ret)if(3*ret not in s):s.add(3*ret)heapq.heappush(lst,3*ret)if(5*ret not in s):s.add(5*ret)heapq.heappush(lst,5*ret)print(ret)return ret

?

方法2：動態規劃

方法1使用動態堆的話，會預先存儲較多的丑數，導致空間復雜度較高。同時，維護最小堆的話也會導致時間復雜度較高。

?

我們可以使用動態規劃的方法：

定義數組dp，其中dp[i]表示第i個丑數（dp[1]=1）

如何得到其他的丑數呢？我們定義三個指針p2，p3，p5，表示下一個預備丑數是當前指針指向的丑數乘以對應的質因數(初始的時候，三個指針的數值都是1）。

對于后面的i，我們令dp[i]=min(dp[p2]*2,dp[p3]*3,dp[p5]*5)，然后分別比較dp[i]和dp[p2]*2，dp[p3]*3，dp[p5]*5是否相等，如果相等則將對應的指針+1。（相等說明這個pi指針代表的數已經被考慮過了（要么是被自己對應的數，要么是被其他數））

?

正確性證明

計算d[i]的時候，指針px的含義是使得dp[j]*x>dp[i-1]的最小下標，即j>=px的時候，dp[j]*x>dp[i-1]；j<px的時候,dp[j]*x<=dp[i-1]。

所以，在計算dp[i]的時候，dp[p2]*2,dp[p3]*3,dp[p5]*5都大于dp[i-1]；同時dp[p2-1]*2,dp[p3-1]*3,dp[p5-1]*5都小于等于dp[i-1]。

令dp[i]=min(dp[p2]*2,dp[p3]*3,dp[p5]*5)，那么這個就是大于dp[i-1]的最小丑數。

圖解

1,一開始，dp[1]=1，三個指針都指向1。

2，計算dp[2]，三個指針都指向1，所以分別乘以因子后是2，3，5；2最小，p2加一，dp[2]=2。

3?計算dp[3]

4 計算dp[4]

5 計算dp[5]

class Solution:def nthUglyNumber(self, n: int) -> int:lst=[0,1]p2=1p3=1p5=1for i in range(2,n+1):lst.append(min(lst[p2]*2,lst[p3]*3,lst[p5]*5))if(lst[i]==lst[p2]*2):p2+=1if(lst[i]==lst[p3]*3):p3+=1if(lst[i]==lst[p5]*5):p5+=1return lst[n]

總結

以上是生活随笔為你收集整理的文巾解题 264. 丑数 II （剑指 Offer 49. 丑数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。