剑指 Offer 49: 丑数

[songyy5517]

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

分析 由题可知，我们需要求得第n个丑数。我们需要解决的问题包括两部分，一是求解各个丑数，二是保证求得的丑数升序排列。丑数有一个很重要的性质：一个丑数乘2，3，5之后还是丑数。因此，我们可以从第一个丑数1出发，分别乘2，3，5自底向上求出之后的丑数。为了保证丑数升序排列，我们可以为2，3，5分别设置三个待乘丑数索引，将索引所在的丑数分别乘2，3，5即可得到三个备选的新丑数，其中的最小值即为最后的新丑数（动态规划）。此外，我们还可以使用最小堆来保存丑数，因为最小堆的堆顶元素总是为最小值，所以我们可以将生成的丑数依次加入最小堆，再从堆中取出元素即可保证顺序。

[songyy5517]

思路1：动态规划，根据已有丑数生成新的丑数

1. 异常处理；
2. 状态定义 & 初始化： （1）创建大小为n的数组 uglies 存放前n个丑数； （2）定义三个变量idx2, idx3, idx5 分别记录三个（已生成的）丑数的索引，这三个丑数分别乘2, 3, 5后大于已有最大丑数的最小丑数；
3. 自底向上计算各个状态：不断根据已有丑数生成下一个丑数： （1）计算三个备选新丑数 $uglies[idx2]\times 2$ , $uglies[idx3]\times 3$ ,和 $uglies[idx5]\times 5$ ，最小值即为下一个丑数；（保证丑数升序排列） （2）更新： 新丑数对应的丑数索引 $idx_n$ 加1； （3）重复上述操作，直到生成了n个丑数；
4. 返回最后的丑数。

复杂度分析：

• 时间复杂度： $O(N)$ ，一共需要生成 $N$ 个丑数，生成每个丑数的时间为 $O(1)$ ；
• 空间复杂度： $O(N)$ ，创建了大小为 $N$ 的数组存放丑数。

[songyy5517]

import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution (int index) {
        // 1. 异常处理
        if (index < 1)
            return 0;

        // 2. 状态定义 & 初始化
        int[] ugly = new int[index];
        ugly[0] = 1;
        int idx_2 = 0, idx_3 = 0, idx_5 = 0;  // 2, 3, 5分别要乘的丑数索引

        // 3. 自底向上生成丑数
        for (int i = 1; i < index; i++) {
            int prod2 = ugly[idx_2] * 2;
            int prod3 = ugly[idx_3] * 3;
            int prod5 = ugly[idx_5] * 5;

            if (prod2 <= prod3 && prod2 <= prod5) {
                ugly[i] = prod2;
                idx_2 ++;
            }

            if (prod3 <= prod2 && prod3 <= prod5) {
                ugly[i] = prod3;
                idx_3 ++;
            }

            if (prod5 <= prod3 && prod5 <= prod2) {
                ugly[i] = prod5;
                idx_5 ++;
            }
        }

        return ugly[index - 1];
    }
}

[songyy5517]

思路2：最小堆 & 哈希表

1. 异常处理；
2. 定义最小堆存放丑数（保证丑数升序），哈希表检查待添加的丑数是否重复，ugly保存从堆中取出的丑数；
3. 初始化：将1加入最小堆和哈希表中；
4. 一共执行index次操作： （1）将最小堆堆顶元素取至ugly变量中； （2）取出的丑数ugly分别乘以2，3，5得到三个新丑数，若哈希表中没有出现，则加入最小堆中。
5. 返回丑数ugly。

复杂度分析

• 时间复杂度： $O(N\log N)$ ， $N$ 为待取丑数的次序，一共需要从最小堆中取N次元素，并且每次将新丑数添加至堆中使用 $O(\log N)$ 大小的时间；
• 空间复杂度： $O(N)$ ，最小堆和哈希表中使用 $O(N)$ 大小的空间。

Key

• 判断重复元素为什么用HashMap，而不是ArrayList？ 因为HashMap.containsKey的时间复杂度为O(1)，而ArrayList.contains的时间复杂度为O(N)。

[songyy5517]

import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution (int index) {
        // 1. 异常处理
        if (index < 1)
            return 0;

        // 2. 定义相关变量：最小堆，哈希表
        PriorityQueue<Long> min_Heap = new PriorityQueue();    //存放丑数
        HashMap<Long, Boolean> uglies = new HashMap();    // 检查元素是否重复

        min_Heap.add((long)1);
        uglies.put((long)1, true);

        long ugly = 1;

        for (int i = 0; i < index; i++){
            // 当前最小丑数
            ugly = min_Heap.remove();

            // 加入新的丑数
            for (int j : new int[]{2, 3, 5}){
                long ugly_j = ugly * j;
                if (!uglies.containsKey(ugly_j)){
                    min_Heap.add(ugly_j);
                    uglies.put(ugly_j, true);
                }
            }
        }

        return (int)ugly;
    }
}

[songyy5517]

2023/3/28 2023/12/6 2024/1/18

1. 重复元素问题
2. 大数问题

2024/4/6

1. 动态规划解法的重复元素问题：for循环都用if，而不是if-else if-else if