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

1. Question

Write a program to find then-th ugly number.
Ugly numbers are positive numbers whose prime factors only include2, 3, 5. For example,1, 2, 3, 4, 5, 6, 8, 9, 10, 12is the sequence of the first10ugly numbers.
Note that1is 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