264.Ugly Number II

Tags: Medium Math Dynamic Programming Heap

Links: https://leetcode.com/problems/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.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

1. 1 is typically treated as an ugly number.
2. n does not exceed 1690.

---

找第n个丑数，肯定不能暴力找了。第一种办法就是利用小根堆来做。下一个丑数一定是从前面的丑数乘上2，3，5其中的一个得到的，每次让小根堆的堆顶为第k个丑数，将这个数字乘上2，3，5的结果推入堆中，为了避免重复的数字，取出堆顶的元素，删掉堆种与它相等的元素。时间复杂度$o(n \log n)$。

class Solution {
public:
    int nthUglyNumber(int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        priority_queue<long long, vector<long long>, greater<long long>> pq;
        pq.push(1);

        for (int i = 1; i < n; ++i) {
            long long tmp = pq.top(); pq.pop();
            while (!pq.empty() && pq.top() == tmp) pq.pop();
            pq.push(tmp * 2), pq.push(tmp * 3), pq.push(tmp * 5);
        }

        return pq.top();
    }
};

第二种解法，用一个数组存储丑数，第n个丑数存储再下标为n-1的位置，分别用p2, p3, p5表示通过乘以2，3，5得到的丑数的上一个位置，开始三个指向0，数组里存储1，对p2, p3, p5指向的数字分别乘以2，3，5，看那个数字最小，最小的就让其下标增加一位。

class Solution {
public:
    int nthUglyNumber(int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<long long> seq(1, 1);
        int p2 = 0, p3 = 0, p5 = 0;
        while (seq.size() < n) {
            long long tmp2 = seq[p2] * 2, tmp3 = seq[p3] * 3, tmp5 = seq[p5] * 5;
            long long res =  min(tmp2, min(tmp3, tmp5));
            seq.push_back(res);

            if (res == tmp2) ++p2;
            if (res == tmp3) ++p3;
            if (res == tmp5) ++p5;
        }

        return seq.back();
    }
};

注意只要14到17行的写法，只要是下一个丑数和产生的临时值相等，就需要移动指针。时间复杂度$O(n)$。