给你一个整数 n
,请你找出并返回第 n
个 丑数 。
丑数 就是只包含质因数 2
、3
和/或 5
的正整数。
示例 1:
输入:n = 10 输出:12 解释:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2:
输入:n = 1 输出:1 解释:1 通常被视为丑数。
提示:
1 <= n <= 1690
方法一:优先队列(最小堆)
初始时,将第一个丑数
时间复杂度
方法二:动态规划
定义数组
定义
当
最后返回
时间复杂度
class Solution:
def nthUglyNumber(self, n: int) -> int:
h = [1]
vis = {1}
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 {
public int nthUglyNumber(int n) {
Set<Long> vis = new HashSet<>();
PriorityQueue<Long> q = new PriorityQueue<>();
int[] f = new int[]{2, 3, 5};
q.offer(1L);
vis.add(1L);
long ans = 0;
while (n-- > 0) {
ans = q.poll();
for (int v : f) {
long next = ans * v;
if (vis.add(next)) {
q.offer(next);
}
}
}
return (int) ans;
}
}
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; ++i) {
int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5;
dp[i] = Math.min(next2, Math.min(next3, next5));
if (dp[i] == next2) ++p2;
if (dp[i] == next3) ++p3;
if (dp[i] == next5) ++p5;
}
return dp[n - 1];
}
}
class Solution {
public:
int nthUglyNumber(int n) {
priority_queue<long, vector<long>, greater<long>> q;
q.push(1l);
unordered_set<long> vis{{1l}};
long ans = 1;
vector<int> f = {2, 3, 5};
while (n--) {
ans = q.top();
q.pop();
for (int& v : f) {
long nxt = ans * v;
if (!vis.count(nxt)) {
vis.insert(nxt);
q.push(nxt);
}
}
}
return (int) ans;
}
};
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n);
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; ++i) {
int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5;
dp[i] = min(next2, min(next3, next5));
if (dp[i] == next2) ++p2;
if (dp[i] == next3) ++p3;
if (dp[i] == next5) ++p5;
}
return dp[n - 1];
}
};
func nthUglyNumber(n int) int {
h := IntHeap([]int{1})
heap.Init(&h)
ans := 1
vis := map[int]bool{1: true}
for n > 0 {
ans = heap.Pop(&h).(int)
for _, v := range []int{2, 3, 5} {
nxt := ans * v
if !vis[nxt] {
vis[nxt] = true
heap.Push(&h, nxt)
}
}
n--
}
return ans
}
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func nthUglyNumber(n int) int {
dp := make([]int, n)
dp[0] = 1
p2, p3, p5 := 0, 0, 0
for i := 1; i < n; i++ {
next2, next3, next5 := dp[p2]*2, dp[p3]*3, dp[p5]*5
dp[i] = min(next2, min(next3, next5))
if dp[i] == next2 {
p2++
}
if dp[i] == next3 {
p3++
}
if dp[i] == next5 {
p5++
}
}
return dp[n-1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
/**
* @param {number} n
* @return {number}
*/
var nthUglyNumber = function (n) {
let dp = [1];
let p2 = 0,
p3 = 0,
p5 = 0;
for (let i = 1; i < n; ++i) {
const next2 = dp[p2] * 2,
next3 = dp[p3] * 3,
next5 = dp[p5] * 5;
dp[i] = Math.min(next2, Math.min(next3, next5));
if (dp[i] == next2) ++p2;
if (dp[i] == next3) ++p3;
if (dp[i] == next5) ++p5;
dp.push(dp[i]);
}
return dp[n - 1];
};
public class Solution {
public int NthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; ++i) {
int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5;
dp[i] = Math.Min(next2, Math.Min(next3, next5));
if (dp[i] == next2) {
++p2;
}
if (dp[i] == next3) {
++p3;
}
if (dp[i] == next5) {
++p5;
}
}
return dp[n - 1];
}
}