傳送門

264. Ugly Number II

? QuestionEditorial Solution ?My Submissions

• Total Accepted:?36259
• Total Submissions:?122710
• Difficulty:?Medium

?

Write a program to find the?n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include?2, 3, 5. For example,?1, 2, 3, 4, 5, 6, 8, 9, 10, 12?is the sequence of the first?10?ugly numbers.

Note that?1?is typically treated as an ugly number.

Show Hint?

Credits:
Special thanks to?@jianchao.li.fighter?for adding this problem and creating all test cases.

?

Subscribe?to see which companies asked this question

Hide Tags ?Dynamic Programming?Heap?Math Show Similar Problems 題解轉自： http://blog.csdn.net/u014673347/article/details/47782645

題意：?
寫一個程序去查找第n個丑數(shù)。丑數(shù)的定義是該數(shù)字只能有2，3，5這樣的因子。1作為第一個丑數(shù)。?
思路：?
我們知道丑數(shù)是由某個丑數(shù)乘上2或者3或者5得來。而且初始化時第一個丑數(shù)是1。

我們將已經按順序求得的丑數(shù)放在數(shù)組中，該數(shù)組初始化時就只有一個1。

接下來考慮將已經求得的數(shù)組中的某個元素乘上2或者3或者5得到下一個應該存入數(shù)組的丑數(shù)。

比如當前的丑數(shù)數(shù)組中最大的值是M，那么下一個丑數(shù)應該是比M大的丑數(shù)。挑一個丑數(shù)乘上2，挑一個丑數(shù)乘上3，挑一個丑數(shù)乘上5，這三個結果都需要大于M。所以乘上2的那個丑數(shù)需要大于M/2,而乘上3的那個丑數(shù)需要大于M/3,乘上5的那個丑數(shù)應該大于M/5。

我們使用一個數(shù)組保存2，3，5接下來乘的那個丑數(shù)的下標，使得結果都大于M。

這個丑數(shù)的下標什么時候用來更新呢？初始化時下標都為0，因為這個時候丑數(shù)數(shù)組中只有一個元素1。當將M加入到數(shù)組后，把2，3，5對應的下標各自往后移動，使得乘的結果大于M。?
以上。?

1 class Solution { 2 public: 3 int nthUglyNumber(int n) { 4 vector<int> dp(n); 5 int index_2 = 0, index_3 = 0, index_5 = 0; 6 int val_2 = 2, val_3 = 3, val_5 = 5; 7 int i = 1; 8 dp[0] = 1; 9 for(;i < n;i++){ 10 int val = min(val_2, min(val_3, val_5) ); 11 if(val == val_2) {dp[i] = val_2; index_2++; val_2 = dp[index_2] * 2;} 12 if(val == val_3) {dp[i] = val_3; index_3++; val_3 = dp[index_3] * 3;} 13 if(val == val_5) {dp[i] = val_5; index_5++; val_5 = dp[index_5] * 5;} 14 } 15 return dp[n - 1]; 16 } 17 };

?

轉載于:https://www.cnblogs.com/njczy2010/p/5708377.html

總結

以上是生活随笔為你收集整理的leetcode 264. Ugly Number II的全部內容，希望文章能夠幫你解決所遇到的問題。

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