Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/264.html
264 Ugly Number II
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.
@tag-array
Algorithm
Each sublist is an ugly number multiplied by 2, 3, 5,
The required ugly number is taken from the generated sequence,
Every time, the smallest one from the three lists is added to the sequence.
We can maintain three lists of ugly numbers:
1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2, 9*2
1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3, 8*3
1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5, 8*5
Carefully observe the above three lists, you can find that each sublist is an ugly number multiplied by 2, 3, 5, and the required ugly number is taken from the generated sequence, each time from the three lists to take out the smallest one to join the sequence.
Step by step example:
[1]
1,1,1
[1, 2]
2,1,1
[1, 2, 3]
2,2,1
[1, 2, 3, 4]
3,2,1
[1, 2, 3, 4, 5]
3,2,2
[1, 2, 3, 4, 5, 6]
4,3,2
[1, 2, 3, 4, 5, 6, 8]
5,3,2
[1, 2, 3, 4, 5, 6, 8, 9]
5,4,2
[1, 2, 3, 4, 5, 6, 8, 9, 10]
6,4,3
Code
Java
-
import java.util.ArrayList; import java.util.List; public class Ugly_Number_II { public static void main(String[] args) { Ugly_Number_II out = new Ugly_Number_II(); Solution s = out.new Solution(); System.out.println(s.nthUglyNumber(10)); } public class Solution { public int nthUglyNumber(int n) { if (n <= 0) { return 0; } List<Integer> nums = new ArrayList<>(); nums.add(1); int i2 = 0; int i3 = 0; int i5 = 0; while (nums.size() < n) { int m2 = nums.get(i2) * 2; int m3 = nums.get(i3) * 3; int m5 = nums.get(i5) * 5; int mn = Math.min(Math.min(m2, m3), m5); nums.add(mn); if (mn == m2) { i2++; } if (mn == m3) { // @note: 3*2 and 2*3 are both 6, so cannot else-if i3++; } if (mn == m5) { i5++; } } return nums.get(nums.size() - 1); } } }
-
// OJ: https://leetcode.com/problems/ugly-number-ii/ // Time: O(N) // Space: O(N) class Solution { public: int nthUglyNumber(int n) { vector<int> num(n); num[0] = 1; int i = 0, j = 0, k = 0; for (int t = 1; t < n; ++t) { num[t] = min({ num[i] * 2, num[j] * 3, num[k] * 5 }); if (num[t] == num[i] * 2) ++i; if (num[t] == num[j] * 3) ++j; if (num[t] == num[k] * 5) ++k; } return num.back(); } };
-
class Solution: def nthUglyNumber(self, n: int) -> int: dp = [1] * n p2 = p3 = p5 = 0 for i in range(1, n): next2, next3, next5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5 dp[i] = min(next2, next3, next5) if dp[i] == next2: p2 += 1 if dp[i] == next3: p3 += 1 if dp[i] == next5: p5 += 1 return dp[n - 1] ############ class Solution: def nthUglyNumber(self, n: int) -> int: h = [1] # heap vis = {1} # hashtable to de-dup ans = 1 for _ in range(n): ans = heappop(h) for v in [2, 3, 5]: nxt = ans * v if nxt not in vis: vis.add(nxt) heappush(h, nxt) return ans class Solution: def nthUglyNumber(self, n: int) -> int: dp = [1] * n p2 = p3 = p5 = 0 for i in range(1, n): next2, next3, next5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5 dp[i] = min(next2, next3, next5) if dp[i] == next2: p2 += 1 if dp[i] == next3: p3 += 1 if dp[i] == next5: p5 += 1 return dp[-1] ############ class Solution(object): def nthUglyNumber(self, n): """ :type n: int :rtype: int """ dp = [0] * (n + 1) dp[1] = 1 i2 = i3 = i5 = 1 for i in range(2, n + 1): dp[i] = min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5) if dp[i] == dp[i2] * 2: i2 += 1 if dp[i] == dp[i3] * 3: i3 += 1 if dp[i] == dp[i5] * 5: i5 += 1 return dp[-1]