【剑指Offer】面试题49：丑数

发表于 | 分类于 | 阅读次数:

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

思路 1：从小到大遍历正整数

最直接的思路是：从小到大遍历正整数，一个一个判断是不是丑数，直到第 1500 个为止。这个算法需要判断某个正整数是不是丑数，如何判断呢？连续除以 2，直到余数不等于 0 为止；连续除以 3，直到余数不等于 0 为止；连续除以 5 直到余数不等于 0 为止；最后剩下的数字如果等于 0 则为丑数，否则不是丑数。

这个算法的缺陷在于，需要判断很多不是丑数的正整数，时间效率不是太高。

思路 2：利用生成丑数的规律

上一种思路的缺陷在于需要判断很多不是丑数的正整数，如何避免这种缺陷呢？我们可以利用丑数的生成规律：丑数总是由丑数乘 2、3 或 5 生成的。我们通过举例来进一步分析一下：

  1. 通过乘 2 所生成的丑数有：1*2、2*2、3*2、4*2、5*2、6*2、8*2、9*2、10*2、12*2、……
  2. 通过乘 3 所生成的丑数有：1*3、2*3、3*3、4*3、5*3、6*3、8*3、9*3、10*3、12*3、……
  3. 通过乘 5 所生成的丑数有：1*5、2*5、3*5、4*5、5*5、6*5、8*5、9*5、10*5、12*5、……

但是我们需要找到第 1500 个丑数，也就是说丑数需要按顺序排放。使用一个数组存放丑数，然后可以利用 3 个游动指针 $T_2$、$T_3$ 和 $T_5$分别来记录数组中 2、3 和 5 的当前的最小丑数。每次比较 $T_2*2$、$T_3*3$ 和 $T_5*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
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        // 特殊输入的检查
        if (index < 1)
            return 0;
        if (index == 1)
            return 1;

        // 指针法
        int[] uglyNums = new int[index];
        uglyNums[0] = 1;
        int pos2 = 0, pos3 = 0, pos5 = 0;
        for (int i = 1; i < index; i++) {
            int n2 = uglyNums[pos2] * 2;
            int n3 = uglyNums[pos3] * 3;
            int n5 = uglyNums[pos5] * 5;
            int newUglyNum = Math.min(n2, Math.min(n3, n5));
            uglyNums[i] = newUglyNum;
            if (n2 == newUglyNum)
                pos2++;
            if (n3 == newUglyNum)
                pos3++;
            if (n5 == newUglyNum)
                pos5++;
        }

        return uglyNums[index - 1];
    }
}