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


解题思路

从丑数的定义我们知道,一个丑数的因子只有 2、3、5,那么丑数 p = 2 ^ x * 3 ^ y * 5 ^ z,即一个丑数一定由另一个丑数乘以 2 或者乘以 3 或者乘以 5 得到。1 是第一个丑数,我们从 1 开始乘以 2、3、5 就得到 2、3、5 三个丑数,从这三个丑数出发再乘以 2、3、5 就得到 4、6、10、6、9、15、10、15、25 九个丑数。明显发现这样子得到的丑数不仅出现重复,而且还是无序的。

一个数分别乘以 2、3、5 可以得到三个不同的丑数,因此我们可以维护三个队列,用于存放一个丑数分别乘以 2、3、5 对应得到的丑数,与此同时,我们还要有一个数组,用于存放当前这个丑数

  • 丑数数组:1
  • 乘以 2 的队列:2
  • 乘以 3 的队列:3
  • 乘以 5 的队列:5
    选择三个队列中最小的一个数 2 加入数组,同时将该最小的数乘以 2、3、5 放入三个队列
  • 丑数数组:1、2
  • 乘以 2 的队列:4
  • 乘以 3 的队列:3、6
  • 乘以 5 的队列:5、10
    选择三个队列中最小的一个数 3 加入数组,同时将该最小的数乘以 2、3、5 放入三个队列
  • 丑数数组:1、2、3
  • 乘以 2 的队列:4、6
  • 乘以 3 的队列:6、9
  • 乘以 5 的队列:5、10、15
    。。。。。。

于是我们就可以得到按从小到大的顺序的第 N 个丑数

实际上我们也没必要维护三个队列,只需要三个指针即可,分别为 p2、p3、p5,表示乘以 2,乘以 3,乘以 5。指针对应数组中的数乘以对应的质因子,就是对应队列中最小的丑数

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index < 1) {
            return 0;
        }
        int[] result = new int[index];
        int p2 = 0, p3 = 0, p5 = 0;
        result[0] = 1;
        for(int i = 1; i < index; i++) {
            result[i] = Math.min(result[p2]*2, Math.min(result[p3]*3, result[p5]*5));
            if(result[i] == result[p2]*2)    p2++;
            if(result[i] == result[p3]*3)    p3++;
            if(result[i] == result[p5]*5)    p5++;
        }
        return result[index - 1];
    }
}

内容来源于网络如有侵权请私信删除