Ricky.L的随笔
0%

LeetCode.264.丑数 II（中等）

发表于 更新于 分类于 Disqus：

题目

264. 丑数 II（中等）

给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
提示：1 <= n <= 1690

题解

解法1：优先队列

根据丑数定义，除了1这个丑数，其他丑数都是从小的丑数乘以2或3或5得到，那么递推就好了。

主要问题是，几个小的丑数乘以2、3、5后的丑数，你不知道哪个大哪个小，不好确定下一个丑数是哪个。比如：

  1. 丑数3乘以质因数后得到丑数：6、9、15。
  2. 丑数4乘以质因数后得到丑数：8、12、20。

所以需要排个序，由于参与排序的元素位置和个数并不确定，所以需要在线算法实现，优先队列（堆）恰好适合元素不确定的排序，入队和出队时调整堆只需要O(log n)的时间复杂度。

还有个问题是要去重，比如 丑数4 * 3 = 12， 丑数6 * 2 = 12，丑数肯定不重复，从优先队列取出元素后，检查有重复去去除即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*

class Solution {
    fun nthUglyNumber(n: Int): Int {
        // 默认是小顶堆
        val pq = PriorityQueue<Long>()
        var u = 1L
        for (i in 2..n) {
            pq.add(u * 2)
            pq.add(u * 3)
            pq.add(u * 5)
            u = pq.remove()
            while (pq.isNotEmpty() && pq.peek() == u) pq.remove()
        }
        return u.toInt()
    }
}

也可以用哈希表来去重，用空间换时间，出队入队还是要占用一点不必要的时间的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*

class Solution {
    fun nthUglyNumber(n: Int): Int {
        // 默认是小顶堆
        val pq = PriorityQueue<Long>()
        val visited = mutableSetOf<Long>()
        val factors = intArrayOf(2, 3, 5)
        var u = 1L
        for (i in 2..n) {
            for (factor in factors) {
                val nextU = u * factor
                if (!visited.contains(nextU)) {
                    pq.add(nextU)
                    visited.add(nextU)
                }
            }
            u = pq.remove()
        }
        return u.toInt()
    }
}

解法2：三指针

3个质因数都要跟每个丑数乘一次，相当于形成3个丑数序列，每次取3个序列中最小值，作为新数组的元素，这很像归并排序，可以用3个指针3路归并。

已经递推出来的丑数要用数组记录下来，因为3个指针位置不确定，可能某个指针会访问到以前较小的丑数。

由于不能有重复值，再取完3个序列左边最小值后，要把相同值给跳过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    fun nthUglyNumber(n: Int): Int {
        var p2 = 1
        var p3 = 1
        var p5 = 1
        val u = IntArray(n + 1) { 0 }
        u[1] = 1
        for (i in 2..n) {
            val v2 = u[p2] * 2
            val v3 = u[p3] * 3
            val v5 = u[p5] * 5
            val nextU = minOf(v2, v3, v5)
            // 多个序列有重复元素要跳过，丑数不能有重复
            if (nextU == v2) p2++
            if (nextU == v3) p3++
            if (nextU == v5) p5++
            u[i] = nextU
        }
        return u[n]
    }
}