描述

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

示例

输入：7
返回值：8

引言

对于这种看似复杂的题目，不妨先通过简单的例子计算，进而推到出完整过程

知识点：
难度：⭐⭐⭐

题解

解题思路

相当于数学推导，先用简单的例子在纸上画出过程，便能用代码实现

方法一：数学模拟

图解

算法流程：

定义三个指针: 三个指针分别用于指向arr中存放的最大丑数下标
每次 res 保存：每次从三个指针指向的数分别计算后的最小的数
数组 arr 用于保存升序的丑数
从1 开始到 index，每次保存乘以 2、3、5 后的较小的数，作为新的丑数，依次类推
从三个指针中选出乘后的最小的丑数后，根据结果进行判断后更新对应指针，用于下次计算最小丑数

Java 版本代码如下：

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        // 小于7的数质因子只包含2、3、5
        if(index < 7) {
            return index;
        }
        // 三个指针分别用于指向arr中存放的最大丑数下标
        // res保存每次从三个指针指向的数分别计算后的最小的数，1为最小丑数
        int p2 = 0, p3 = 0, p5 = 0, res = 1;
        // 用于保存顺序的丑数
        int[] arr = new int[index + 1];
        // 先保存最小丑数1
        arr[0] = res;
        // 从第2个树开始查找，因为第一个丑数已经设定为 1
        int idx = 1;
        // 只需要查找 index-1 次即可，因为第1个丑数为1已经找出
        // 加入要找到第 7 个丑数，只需要查找6次即可
        while(--index > 0) {
            // 从三个指针中选出乘后的最小的丑数
            res = Math.min(arr[p2] * 2, Math.min(arr[p3] * 3, arr[p5] * 5));
            // 更新指针
            if(arr[p2] * 2 == res) {
                p2++;
            } 
            if(arr[p3] * 3 == res) {
                p3++;
            }
            if(arr[p5] * 5 == res) {
                p5++;
            }
            // 每次添加当次操作的最小丑数
            arr[idx++] = res;
        }
        return res;
    }
}

Python 版本代码如下：

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index == 0:
            return 0
        mat,a,b,c = [1]*index,0,0,0
        for i in range(1,index):
            mat[i] = min(mat[a]*2, mat[b]*3, mat[c]*5)
            if mat[i] == mat[a]*2:
                a += 1
            if mat[i] == mat[b]*3:
                b += 1
            if mat[i] == mat[c]*5:
                c += 1

        return mat[-1]

复杂度分析：

时间复杂度 O(N)：从 1 到 index 循环 N 次，N 为 index 值

空间复杂度 O(N)：使用长度为 N 的数组保存顺序的丑数结果

丑数（分治+归并）

描述