Problem
Write a program to find the n
-th ugly number.
Ugly numbers are** positive numbers** whose prime factors only include 2, 3, 5
.
Example:
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
**Note: **
1
is typically treated as an ugly number.n
does not exceed 1690.
Solution
/**
* @param {number} n
* @return {number}
*/
var nthUglyNumber = function(n) {
if (n < 1) return 0;
var dp = [1];
var t2 = 0;
var t3 = 0;
var t5 = 0;
for (var i = 1; i < n; i++) {
dp[i] = Math.min(dp[t2] * 2, dp[t3] * 3, dp[t5] * 5);
if(dp[i] === dp[t2]*2) t2++;
if(dp[i] === dp[t3]*3) t3++;
if(dp[i] === dp[t5]*5) t5++;
}
return dp[n - 1];
};
Explain:
- 除了
1
,其它结果都是以前的结果乘2
,3
,5
得来的; dp[i] = min(dp[t2] * 2, dp[t3] * 3, dp[t5] * 5)
,t2
,t3
,t5
是上一次乘2
,3
,5
的时候;
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).