ChunNote
0%

leetCode-264:Ugly Number II

发表于 分类于

问题描述

给定一个正整数 n，要求找出第 n 个“丑数”。“丑数”定义：只能被 2、3、5 整除的正整数（1 是“丑数”）。题目链接：**点我**

样例输入输出

输入：10

输出：12

解释：“丑数”序列为：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]，第10个数为12

输入：1

输出：1

问题解法

最简单粗暴的方法是对每个正整数依次判断是否是“丑数”，至到找到第 n 个数为止。但是这样做太耗时间。仔细观察“丑数”的定义，可以发现对于大于 1 的正整数，一个数要成为“丑数”，其必须是 2、3、5 的倍数。因此可以简化操作：对每个“丑数”，分别乘以 2、3、5 ，得到新的“丑数”，对这些“丑数”进行排序，取出第 n 个数即可。这里可以使用最小堆来实现。但是最小堆内部依赖排序，其时间复杂度为 O(nlgn)，仍然偏大了一点，可以继续优化。

使用类似归并排序的做法，使用 3 路来分别计算当前路径的“丑数”与 2、3、5 相乘的值，每次取出最小的值放入“丑数”列表中，同时更新当前路径的“丑数”，将其更新为：“丑数”列表中，刚才剔除的“丑数”的下一个“丑数”。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution
{
    public int nthUglyNumber(int n)
    {
        int[] nums = {2, 3, 5};
        int[] points = {0, 0, 0};
        int[] currents = new int[3];
        int[] results = new int[n];
        results[0] = 1;
        int index = 1;
        for (int i = 2; i <= n; i++)
        {
            int minNum = Integer.MAX_VALUE;
            for (int j = 0; j < 3; j++)
            {
                currents[j] = nums[j] * results[points[j]];
                minNum = Math.min(minNum, currents[j]);
            }

            for (int j = 0; j < 3; j++)
            {
                if (currents[j] == minNum)
                {
                    points[j]++;
                }
            }

            results[index] = minNum;
            index++;
        }
        return results[n - 1];
    }
}