丑数 详解

丑数（Ugly Number）是计算机科学和数学中的一个经典问题。以下是关于丑数的定义、特性、算法和应用的详解。

1. 什么是丑数？

定义

丑数是 只包含质因数 2、3 和 5 的正整数。

• 丑数的集合：$$1,2,3,4,5,6,8,9,10,12,15,\dots$$
  • $1$通常被定义为丑数（尽管它没有质因数）。
  • 非丑数：如$7,11,14,19$等，包含其他质因数。

丑数的递推定义

1. $1$是丑数。
2. 如果$x$是丑数，则$x\times 2$、$x\times 3$、$x\times 5$也是丑数。
3. 丑数集合是通过这种递推生成的。

2. 丑数的特性

1. 正整数：

   • 丑数必须是正整数，负数和 0 都不是丑数。

2. 有限质因数：

   • 丑数的质因数只能是$2,3,5$。

3. 数学表示：

   • 一个数$n$是丑数，当且仅当它可以表示为：
     $$n=2^a\times 3^b\times 5^c(a,b,c\ge 0)$$

   • 如$6=2^1\times 3^1$、$8=2^3$都是丑数。

3. 丑数的判定

算法：判断一个数是否是丑数

思路

• 不断用$2,3,5$去除$n$，直到$n=1$：
  • 如果最后剩下$1$，说明$n$只包含$2,3,5$的因数，是丑数。
  • 如果最后剩下其他质因数，则$n$不是丑数。

代码实现

public class UglyNumber {
    public boolean isUgly(int n) {
        if (n <= 0) {
            return false; // 非正整数不是丑数
        }
        while (n % 2 == 0) {
            n /= 2; // 去掉因数 2
        }
        while (n % 3 == 0) {
            n /= 3; // 去掉因数 3
        }
        while (n % 5 == 0) {
            n /= 5; // 去掉因数 5
        }
        return n == 1; // 判断是否只剩下 1
    }

    public static void main(String[] args) {
        UglyNumber uglyNumber = new UglyNumber();
        System.out.println(uglyNumber.isUgly(6));  // true
        System.out.println(uglyNumber.isUgly(14)); // false
        System.out.println(uglyNumber.isUgly(1));  // true
    }
}

时间复杂度

• 最坏情况下的时间复杂度为$O(\log n)$，因为每次去除一个因数都会缩小$n$。

4. 丑数的生成

(1) 找到第$n$个丑数

思路：动态规划

• 使用一个数组 dp 存储前$n$个丑数，按顺序生成。
• 定义$dp[1]=1$。
• 利用三个指针$p2,p3,p5$，分别表示下一个乘以$2,3,5$的丑数。
• 每次选取最小值作为下一个丑数。

代码实现

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

        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];
    }

    public static void main(String[] args) {
        NthUglyNumber nthUgly = new NthUglyNumber();
        System.out.println(nthUgly.nthUglyNumber(10)); // 输出 12
    }
}

输出

• 输入$n=10$，输出$12$（前 10 个丑数：$$1,2,3,4,5,6,8,9,10,12$$）。

时间复杂度

• $O(n)$：每次计算最小值需要常数时间。

(2) 丑数的快速生成

如果需要快速生成大量丑数，可以使用最小堆（PriorityQueue）。

思路

• 使用最小堆动态生成丑数：
  1. 初始化堆，将第一个丑数$1$放入。
  2. 每次弹出堆顶，将其乘以$2,3,5$后的值加入堆。
  3. 使用 Set 去重，防止重复。

代码实现

import java.util.*;

public class NthUglyNumberHeap {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> heap = new PriorityQueue<>();
        Set<Long> seen = new HashSet<>();

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

        int[] factors = {2, 3, 5};
        long ugly = 1;

        for (int i = 0; i < n; i++) {
            ugly = heap.poll(); // 弹出最小值
            for (int factor : factors) {
                long next = ugly * factor;
                if (!seen.contains(next)) {
                    heap.add(next);
                    seen.add(next);
                }
            }
        }
        return (int) ugly;
    }

    public static void main(String[] args) {
        NthUglyNumberHeap nthUgly = new NthUglyNumberHeap();
        System.out.println(nthUgly.nthUglyNumber(10)); // 输出 12
    }
}

输出

• 输入$n=10$，输出$12$。

时间复杂度

• $O(n\log n)$：每次操作堆需要$O(\log n)$。

5. 丑数的应用

(1) 图形学和渲染

• 在计算机图形学中，丑数用于生成平滑的缩放和分辨率变化。

(2) 分布式计算

• 丑数在某些调度算法中用于均匀分布计算任务。

(3) 数学建模

• 丑数问题在质因数分解和整数建模中具有理论意义。

6. 总结

适合不同场景

• 小规模问题：判断单个数是否是丑数。
• 生成序列：使用动态规划生成前$n$个丑数。
• 并行化或大规模生成：使用堆方法。

丑数是动态规划和最小堆的经典应用问题之一，通过理解其生成规则和算法，可以高效解决类似问题。