LeetCode 剑指 Offer 49. 丑数

Categories:

题目描述
思路分析
1. 解法一：多指针 DP（推荐）
相似题目

题目描述

✅ 剑指 Offer 49. 丑数

思路分析

解法一：多指针 DP（推荐）

核心思路：

丑数只能由 2、3、5 乘出来。

使用三个指针分别指向下一个乘以 2、3、5 的位置。

每次取最小值并移动对应指针，避免重复。

复杂度分析：

时间复杂度：O(n)，其中 n 表示第 n 个丑数。

空间复杂度：O(n)，用于 DP 数组。

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;

        int i2 = 0;
        int i3 = 0;
        int i5 = 0;

        for (int i = 1; i < n; i++) {
            int next = Math.min(dp[i2] * 2, Math.min(dp[i3] * 3, dp[i5] * 5));
            dp[i] = next;

            if (next == dp[i2] * 2) {
                i2++;
            }
            if (next == dp[i3] * 3) {
                i3++;
            }
            if (next == dp[i5] * 5) {
                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++ {
		next := dp[i2] * 2
		if v := dp[i3] * 3; v < next {
			next = v
		}
		if v := dp[i5] * 5; v < next {
			next = v
		}

		dp[i] = next
		if next == dp[i2]*2 {
			i2++
		}
		if next == dp[i3]*3 {
			i3++
		}
		if next == dp[i5]*5 {
			i5++
		}
	}

	return dp[n-1]
}

相似题目

题目	难度	考察点
263. 丑数	简单	数学
264. 丑数 II	中等	多指针
313. 超级丑数	中等	多指针
1201. 丑数 III	中等	数学
878. 第 N 个神奇数字	困难	数学

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/77387514