LeetCode 264. 丑数 II

Categories:

Tags:

题目描述
思路分析
1. 解法一：三指针动态规划（推荐）
2. 解法二：最小堆
相似题目

题目描述

✅ 264. 丑数 II

思路分析

解法一：三指针动态规划（推荐）

核心思路：

丑数序列可以看作由前面的丑数分别乘以 2、3、5 得到的三个有序子序列合并而成。

维护三个指针 p2、p3、p5，分别指向下一个待乘以 2、3、5 的丑数位置。

每次取 dp[p2]*2、dp[p3]*3、dp[p5]*5 三者的最小值作为下一个丑数。

哪个指针对应的乘积最小，就将该指针向前移动一步（注意可能同时有多个指针需要前进，以避免重复）。

dp[0] = 1，第一个丑数为 1，循环从索引 1 开始直到填满 n 个丑数。

复杂度分析：

时间复杂度：O(n)，其中 n 为目标丑数的序号，每个丑数只计算一次。

空间复杂度：O(n)，使用长度为 n 的 dp 数组存储所有丑数。

class Solution {
  public int nthUglyNumber(int n) {
    int[] dp = new int[n];
    // 第一个丑数是 1
    dp[0] = 1;

    // 三个指针分别指向下一个待乘以 2、3、5 的丑数位置
    int p2 = 0, p3 = 0, p5 = 0;

    for (int i = 1; i < n; i++) {
      int next2 = dp[p2] * 2;
      int next3 = dp[p3] * 3;
      int 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];
  }
}

func nthUglyNumber(n int) int {
	dp := make([]int, n)
	// 第一个丑数是 1
	dp[0] = 1

	// 三个指针分别指向下一个待乘以 2、3、5 的丑数位置
	p2, p3, p5 := 0, 0, 0

	for i := 1; i < n; i++ {
		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]
}

解法二：最小堆

核心思路：

使用最小堆（优先队列）维护候选丑数集合，初始将 1 入堆。

每次从堆顶取出最小值作为当前丑数，然后将其乘以 2、3、5 的结果压入堆中。

为避免重复，使用哈希集合记录已入堆的数字。

重复执行 n 次，第 n 次取出的即为第 n 个丑数。

复杂度分析：

时间复杂度：O(n log n)，其中 n 为目标丑数的序号，每次堆操作为 O(log n)。

空间复杂度：O(n)，堆和哈希集合中最多存储 O(n) 个元素。

class Solution {
  public int nthUglyNumber(int n) {
    // 最小堆，存储候选丑数
    PriorityQueue<Long> heap = new PriorityQueue<>();
    // 哈希集合，避免重复入堆
    Set<Long> seen = new HashSet<>();

    heap.offer(1L);
    seen.add(1L);

    long[] factors = {2L, 3L, 5L};
    long curr = 1L;

    for (int i = 0; i < n; i++) {
      curr = heap.poll();
      // 将当前丑数乘以 2、3、5 后的结果加入候选集
      for (long f : factors) {
        long next = curr * f;
        if (seen.add(next)) {
          heap.offer(next);
        }
      }
    }

    return (int) curr;
  }
}

import "container/heap"

// IntHeap 是 int64 的最小堆
type IntHeap []int64

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.(int64)) }
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func nthUglyNumber(n int) int {
	h := &IntHeap{1}
	heap.Init(h)
	// 哈希集合，避免重复入堆
	seen := map[int64]bool{1: true}
	factors := []int64{2, 3, 5}

	var curr int64
	for i := 0; i < n; i++ {
		curr = heap.Pop(h).(int64)
		// 将当前丑数乘以 2、3、5 后的结果加入候选集
		for _, f := range factors {
			next := curr * f
			if !seen[next] {
				seen[next] = true
				heap.Push(h, next)
			}
		}
	}

	return int(curr)
}

相似题目

题目	难度	考察点
263. 丑数	简单	数学 / 因子判断
313. 超级丑数	中等	动态规划 / 多指针
1201. 丑数 III	中等	二分查找 / 容斥原理
378. 有序矩阵中第 K 小的元素	中等	堆 / 二分查找
373. 查找和最小的 K 对数字	中等	堆 / 多路归并
218. 天际线问题	困难	堆 / 扫描线

本文作者: HGNULB

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