A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Leetcode
Math
Tree
Graph
Two Pointers
Linked List
Topological Sort
Hash Table
Trie
Sort
Binary Search
Heap
215 Kth Largest Element in an Array
239 Sliding Window Maximum
253 Meeting Rooms II
264 Ugly Number II
295 Find Median from Data Stream
313 Super Ugly Number
347 Top K Frequent Elements
358 Rearrange String k Distance Apart
373 Find K Pairs with Smallest Sums
378 Kth Smallest Element in a Sorted Matrix
407 Trapping Rain Water II
451 Sort Characters By Frequency
480 Sliding Window Median
502 IPO
659 Split Array into Consecutive Subsequences
668 Kth Smallest Number in Multiplication Table
692 Top K Frequent Words
759 Employee Free Time
767 Reorganize String
778 Swim in Rising Water
Breadth First Search
Stack
Backtracking
Dynamic Programming
Union Find
Scan Line
String
Reservoir Sampling
Recursion
Google
Powered By
GitBook
264 Ugly Number II
264.
Ugly Number II
1. Question
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, and n
does not exceed 1690
.
2. Implementation
(1) Heap
1
class
Solution
{
2
public
int
nthUglyNumber
(
int
n
)
{
3
PriorityQueue
<
Long
>
minHeap
=
new
PriorityQueue
<>
();
4
minHeap
.
add
(
1L
);
5
6
long
curNum
=
0
;
7
for
(
int
i
=
0
;
i
<
n
;
i
++
)
{
8
curNum
=
minHeap
.
remove
();
9
10
while
(
!
minHeap
.
isEmpty
()
&&
minHeap
.
peek
()
==
curNum
)
{
11
curNum
=
minHeap
.
remove
();
12
}
13
14
minHeap
.
add
(
2
*
curNum
);
15
minHeap
.
add
(
3
*
curNum
);
16
minHeap
.
add
(
5
*
curNum
);
17
}
18
return
(
int
)
curNum
;
19
}
20
}
Copied!
3. Time & Space Complexity
Heap:
时间复杂度O(n * logn), 空间复杂度O(n)
Previous
253 Meeting Rooms II
Next
295 Find Median from Data Stream
Last modified
2yr ago
Copy link
Contents
264. Ugly Number II
1. Question
2. Implementation
3. Time & Space Complexity