leetcode263-264-313.ugly numbers

发表于 更新于 分类于 ，

前言

这一篇博客把ugly numbers系列的题目做一个整理。这三道题正好是一个思路的循序渐进，所以放在一篇博客当中。

Ugly Number

1
2
3
4
5
6
Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 
For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

丑数是指只包含2,3,5质因数的数。因此6,8是丑数因为6=2*3,8=2*2*2，而14不是丑数因为14包含质因数7。现在写一个方法判断一个数字是否是丑数。

这题只需要将所有的2，3，5质数消去之后，余下的质数是不是1来进行判断。代码如下：

1
2
3
4
5
6
7
public boolean isUgly(int num) {
    if(num <= 0) return false;
    while(num % 2 == 0) num /= 2;
    while(num % 5 == 0) num /= 5;
    while(num % 3 == 0) num /= 3;
    return num == 1;
}

264. Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

这道题目在上一题定义的基础上，要找到第n个丑数。

这题可以使用暴力遍历法，从1开始，对每一个数都进行判断，直到找到第n个丑数为止。但是这样的方法效率很差。所以需要寻找一下这些数之间的规律，从而找到更好的解决方法。

这里运用了Dynamic Programming的编程思想来解决。现在我们可以将丑数完整的归入以下三类：

全部丑数： 1,2,3,4,5,6,8…
包含丑数2：1*2,2*2,3*2,4*2,5*2,6*2,8*2…
包含丑数3：1*3,2*3,3*3,4*3,5*3,6*3,8*3…
包含丑数5：1*5,2*5,3*5,4*5,5*5,6*5,7*5…

可以看到，每一个丑数子列上，第i位上的值等于全部丑数的第i个丑数*素数。我们只需要像归并算法中的合并方法那样，将三个子列按照从小到大的情况合并成一个序列即可。

我们从基础情况开始推理，那么每一步的结果如下；

第0步：

全部丑数：1
包含丑数2：2
包含丑数3：3
包含丑数5：5

此时比较三个子序列，得出最小值为2，则更新全部丑数序列，并且更新包含丑数2的子序列，如下：

第1步

全部丑数：1,2
包含丑数2：2,4(2*2)
包含丑数3：3,
包含丑数5：5,

再次比较三个子序列，得出最小值为3，更新方法同上，结果如下：
第2步

全部丑数：1,2,3
包含丑数2：2,4
包含丑数3：3,6(2*3)
包含丑数5：5

按照如上方法我们就可以得出第n个丑数的值。 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int nthUglyNumber(int n) {
    int idx1 = 0, idx2 = 0, idx3 = 0;
    int[] result = new int[n];
    result[0] = 1;
    for(int i = 1 ; i<n ; i++){
        int num1 = result[idx1] * 2;
        int num2 = result[idx2] * 3;
        int num3 = result[idx3] * 5;
        result[i] = Math.min(num1, Math.min(num2, num3));
        if(num1==result[i]) idx1++;
        if(num2==result[i]) idx2++;
        if(num3==result[i]) idx3++;
    }
    return result[n-1];
}

313 Super ugly number

1
2
3
4
5
6
7
8
9
Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

这一题和上一题的变化相比，基本素数从[2,3,5]变成了任意数量的有序素数构成的数组。其实本质上思路还是一样的，我们只需要新建一个数组来存放当前子序列丑数对应的所有丑数的下标就可以了。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int nthSuperUglyNumber(int n, int[] primes) {
    int[] index = new int[primes.length];
    int[] uglyNumbers = new int[primes.length];
    System.arraycopy(primes, 0, uglyNumbers, 0, primes.length);
    
    int[] result = new int[n];
    result[0] = 1;
    for(int i = 1 ; i<n ; i++){
        result[i] = Integer.MAX_VALUE;
        for(int j = 0 ; j<uglyNumbers.length ; j++){
            if(uglyNumbers[j] < result[i]) result[i] = uglyNumbers[j];
        }
        for(int j = 0 ; j <uglyNumbers.length ; j++){
            if(uglyNumbers[j]==result[i]) {
                index[j]++;
                uglyNumbers[j] = primes[j] * result[index[j]];
            }
        }
    }
    return result[n-1];
}

当然，这道题也可以利用特殊的数据结构来完成。优先队列可以很好的满足该情况。我们先将题目中提供的所有素数输入到优先队列中，相当于存入了所有的子丑数列的第一个元素。因此每个素数持有的信息包括当前对应的丑数的下标。之后我们可以将比较的任务交给优先队列的完成，我们只需从中提取最小的那个数，加到结果集中，同时别忘了更新各个子序列从而消去出现重复值的情况。

代码如下：

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
34
public int nthSuperUglyNumberHeap(int n, int[] primes) {
    int[] ugly = new int[n];

    PriorityQueue<Num> pq = new PriorityQueue<>();
    for (int i = 0; i < primes.length; i++) pq.add(new Num(primes[i], 1, primes[i]));
    ugly[0] = 1;

    for (int i = 1; i < n; i++) {
        ugly[i] = pq.peek().val;
        while (pq.peek().val == ugly[i]) {
            Num nxt = pq.poll();
            pq.add(new Num(nxt.p * ugly[nxt.idx], nxt.idx + 1, nxt.p));
        }
    }

    return ugly[n - 1];
}

private class Num implements Comparable<Num> {
    int val;
    int idx;
    int p;

    public Num(int val, int idx, int p) {
        this.val = val;
        this.idx = idx;
        this.p = p;
    }

    @Override
    public int compareTo(Num that) {
        return this.val - that.val;
    }
}