LeetCode 264: Ugly Number II (Three-Pointer DP Merge)
LeetCode 264Dynamic ProgrammingThree PointersToday we solve LeetCode 264 - Ugly Number II.
Source: https://leetcode.com/problems/ugly-number-ii/
English
Problem Summary
An ugly number is a positive integer whose prime factors are only 2, 3, and 5. Return the n-th ugly number.
Key Insight
Every ugly number (except 1) can be generated by multiplying a previous ugly number by 2, 3, or 5. So we can build the sequence in sorted order using dynamic programming plus three pointers:
- i2 points to the next base for *2
- i3 points to the next base for *3
- i5 points to the next base for *5
At each step, choose min(dp[i2]*2, dp[i3]*3, dp[i5]*5). If multiple are equal, move all matched pointers to avoid duplicates.
Algorithm
- Initialize dp[0] = 1.
- Maintain pointers i2 = i3 = i5 = 0.
- For each position i from 1 to n-1:
1) Compute candidates next2, next3, next5.
2) Set dp[i] to their minimum.
3) Increment every pointer whose candidate equals dp[i].
- Return dp[n-1].
Complexity Analysis
Time: O(n).
Space: O(n).
Common Pitfalls
- Using if ... else if ... for pointer updates; this creates duplicates.
- Forgetting that the first ugly number is 1.
- Trying to check each integer one by one (too slow compared with direct DP generation).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int i2 = 0, i3 = 0, i5 = 0;
for (int i = 1; i < n; i++) {
int next2 = dp[i2] * 2;
int next3 = dp[i3] * 3;
int next5 = dp[i5] * 5;
int next = Math.min(next2, Math.min(next3, next5));
dp[i] = next;
if (next == next2) i2++;
if (next == next3) i3++;
if (next == next5) i5++;
}
return dp[n - 1];
}
}func nthUglyNumber(n int) int {
dp := make([]int, n)
dp[0] = 1
i2, i3, i5 := 0, 0, 0
for i := 1; i < n; i++ {
next2 := dp[i2] * 2
next3 := dp[i3] * 3
next5 := dp[i5] * 5
next := next2
if next3 < next {
next = next3
}
if next5 < next {
next = next5
}
dp[i] = next
if next == next2 {
i2++
}
if next == next3 {
i3++
}
if next == next5 {
i5++
}
}
return dp[n-1]
}class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n);
dp[0] = 1;
int i2 = 0, i3 = 0, i5 = 0;
for (int i = 1; i < n; ++i) {
int next2 = dp[i2] * 2;
int next3 = dp[i3] * 3;
int next5 = dp[i5] * 5;
int next = min(next2, min(next3, next5));
dp[i] = next;
if (next == next2) ++i2;
if (next == next3) ++i3;
if (next == next5) ++i5;
}
return dp[n - 1];
}
};class Solution:
def nthUglyNumber(self, n: int) -> int:
dp = [0] * n
dp[0] = 1
i2 = i3 = i5 = 0
for i in range(1, n):
next2 = dp[i2] * 2
next3 = dp[i3] * 3
next5 = dp[i5] * 5
nxt = min(next2, next3, next5)
dp[i] = nxt
if nxt == next2:
i2 += 1
if nxt == next3:
i3 += 1
if nxt == next5:
i5 += 1
return dp[-1]var nthUglyNumber = function(n) {
const dp = new Array(n).fill(0);
dp[0] = 1;
let i2 = 0, i3 = 0, i5 = 0;
for (let i = 1; i < n; i++) {
const next2 = dp[i2] * 2;
const next3 = dp[i3] * 3;
const next5 = dp[i5] * 5;
const next = Math.min(next2, next3, next5);
dp[i] = next;
if (next === next2) i2++;
if (next === next3) i3++;
if (next === next5) i5++;
}
return dp[n - 1];
};中文
题目概述
丑数定义为只包含质因子 2、3、5 的正整数。请返回第 n 个丑数。
核心思路
除 1 外，每个丑数都可以由“前面的某个丑数 × 2/3/5”得到。我们用 dp 按从小到大构造序列，再用三个指针维护下一个候选值：
- i2 指向当前用于生成 *2 的位置
- i3 指向当前用于生成 *3 的位置
- i5 指向当前用于生成 *5 的位置
每一步取三个候选值最小者作为下一个丑数。若出现相等（如 6=2×3=3×2），对应指针都要前进，避免重复。
算法步骤
- 初始化 dp[0] = 1。
- 初始化三个指针 i2 = i3 = i5 = 0。
- 从 i=1 到 n-1 循环：
1）计算 next2、next3、next5。
2）取最小值写入 dp[i]。
3）所有等于该最小值的指针都自增。
- 返回 dp[n-1]。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)。
常见陷阱
- 用 if ... else if ... 更新指针，会漏掉并列最小值导致重复。
- 忘记第一个丑数是 1。
- 逐个整数判断是否为丑数，性能不如直接构造序列。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int i2 = 0, i3 = 0, i5 = 0;
for (int i = 1; i < n; i++) {
int next2 = dp[i2] * 2;
int next3 = dp[i3] * 3;
int next5 = dp[i5] * 5;
int next = Math.min(next2, Math.min(next3, next5));
dp[i] = next;
if (next == next2) i2++;
if (next == next3) i3++;
if (next == next5) i5++;
}
return dp[n - 1];
}
}func nthUglyNumber(n int) int {
dp := make([]int, n)
dp[0] = 1
i2, i3, i5 := 0, 0, 0
for i := 1; i < n; i++ {
next2 := dp[i2] * 2
next3 := dp[i3] * 3
next5 := dp[i5] * 5
next := next2
if next3 < next {
next = next3
}
if next5 < next {
next = next5
}
dp[i] = next
if next == next2 {
i2++
}
if next == next3 {
i3++
}
if next == next5 {
i5++
}
}
return dp[n-1]
}class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n);
dp[0] = 1;
int i2 = 0, i3 = 0, i5 = 0;
for (int i = 1; i < n; ++i) {
int next2 = dp[i2] * 2;
int next3 = dp[i3] * 3;
int next5 = dp[i5] * 5;
int next = min(next2, min(next3, next5));
dp[i] = next;
if (next == next2) ++i2;
if (next == next3) ++i3;
if (next == next5) ++i5;
}
return dp[n - 1];
}
};class Solution:
def nthUglyNumber(self, n: int) -> int:
dp = [0] * n
dp[0] = 1
i2 = i3 = i5 = 0
for i in range(1, n):
next2 = dp[i2] * 2
next3 = dp[i3] * 3
next5 = dp[i5] * 5
nxt = min(next2, next3, next5)
dp[i] = nxt
if nxt == next2:
i2 += 1
if nxt == next3:
i3 += 1
if nxt == next5:
i5 += 1
return dp[-1]var nthUglyNumber = function(n) {
const dp = new Array(n).fill(0);
dp[0] = 1;
let i2 = 0, i3 = 0, i5 = 0;
for (let i = 1; i < n; i++) {
const next2 = dp[i2] * 2;
const next3 = dp[i3] * 3;
const next5 = dp[i5] * 5;
const next = Math.min(next2, next3, next5);
dp[i] = next;
if (next === next2) i2++;
if (next === next3) i3++;
if (next === next5) i5++;
}
return dp[n - 1];
};
Comments