LeetCode 313. 超级丑数

Categories:

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

题目描述

✅ 313. 超级丑数

思路分析

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

核心思路：

dp[i] 表示第 i 个超级丑数。

对每个质数维护指针，表示下一个可乘的位置。

每次取最小候选并移动对应指针。

复杂度分析：

时间复杂度：O(nk)，其中 n 表示丑数个数，k 表示质数数量。

空间复杂度：O(n + k)。

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int k = primes.length;
        int[] idx = new int[k];
        int[] dp = new int[n];
        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            long min = Long.MAX_VALUE;
            for (int j = 0; j < k; j++) {
                min = Math.min(min, (long) dp[idx[j]] * primes[j]);
            }
            dp[i] = (int) min;
            for (int j = 0; j < k; j++) {
                if ((long) dp[idx[j]] * primes[j] == min) {
                    idx[j]++;
                }
            }
        }

        return dp[n - 1];
    }
}

func nthSuperUglyNumber(n int, primes []int) int {
	k := len(primes)
	idx := make([]int, k)
	dp := make([]int, n)
	dp[0] = 1

	for i := 1; i < n; i++ {
		min := int64(1<<63 - 1)
		for j := 0; j < k; j++ {
			v := int64(dp[idx[j]]) * int64(primes[j])
			if v < min {
				min = v
			}
		}
		dp[i] = int(min)
		for j := 0; j < k; j++ {
			if int64(dp[idx[j]])*int64(primes[j]) == min {
				idx[j]++
			}
		}
	}

	return dp[n-1]
}

相似题目

题目	难度	考察点
313. 超级丑数	中等	DP
264. 丑数 II	中等	DP
1201. 丑数 III	困难	二分
1482. 制作 m 束花所需的最少天数	中等	二分
279. 完全平方数	中等	DP

本文作者: HGNULB

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