264. Ugly Number II - cocoder39/coco39_LC GitHub Wiki
2020 Notes:
min heap
time complexity is O(N) because we add one element into uglyNumbers each time execute the while loop. Space complexity: uglyNumbers has n elements. We execute while loop n times so we add at most 3n elements into visited and min_heap. Total space complexity is O(N)
class Solution:
def nthUglyNumber(self, n: int) -> int:
DATA = [2, 3, 5]
min_heap = [1]
visited = set(min_heap)
uglyNumbers = []
while len(uglyNumbers) < n:
cur_min = heapq.heappop(min_heap)
uglyNumbers.append(cur_min)
for d in DATA:
next_ugly_num = cur_min * d
if next_ugly_num not in visited:
visited.add(next_ugly_num)
heapq.heappush(min_heap, next_ugly_num)
return uglyNumbers[-1]
Option 2: dp
when ugly_nums[i2] * 2 == ugly_nums[i3] * 3 (eg, 3 * 2 == 2 * 3), we will need to move both i2 and i3
class Solution:
def nthUglyNumber(self, n: int) -> int:
ugly_nums = [1]
i2, i3, i5 = 0, 0, 0
while len(ugly_nums) < n:
next_ugly_num = min(ugly_nums[i2] * 2, ugly_nums[i3] * 3, ugly_nums[i5] * 5)
ugly_nums.append(next_ugly_num)
if next_ugly_num % 2 == 0:
i2 += 1
if next_ugly_num % 3 == 0:
i3 += 1
if next_ugly_num % 5 == 0:
i5 += 1
return ugly_nums[-1]
============================================================================================================
same idea as in 23. Merge k Sorted Lists
bug report: following code would generate bug.
if (p == ugly[u2] * 2)
else if (p == ugly[u3] * 3)
else if (p == ugly[u5] * 5)
int nthUglyNumber(int n) {
int u2 = 0, u3 = 0, u5 = 0; //point to index of an ugly number
vector<int> uglys = {1};
while (uglys.size() < n) {
int num = min(2 * uglys[u2], min(3 * uglys[u3], 5 * uglys[u5]));
uglys.push_back(num);
if (num % 2 == 0) {
u2++;
}
if (num % 3 == 0) {
u3++;
}
if (num % 5 == 0) {
u5++;
}
}
return uglys.back();
}