剑指offer：丑数

题目链接

NowCoder

题目描述

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

解题思路

丑数是只包含质因子2、3和5的数，因此任何一个丑数的因数都是丑数，任何一个丑数乘以 2、3、5 都能得到丑数。假设有一个丑数序列，包含 n 个丑数，那么第 n + 1 个丑数一定是前 n 个丑数中乘以 2、3、5 中第 n + 1大的数。

假设现在有丑数序列：<1, 2, 3>

将现有丑数序列乘以 2, 3, 5 分别得到：

• 乘以 2 的队列：4， 6
• 乘以 3 的队列：6，9
• 乘以 5 的队列：5， 10， 15

因为三个队列都是按照从小到大排序，因此三个队首的最小值即为下一个插入队列中的数。此时的最小值为 4，将 4 插入丑数队列，并将 4 从三个队列中剔除。

此时的丑数序列为：<1, 2, 3, 4>

将新加入的丑数乘以 2、3、5 插入到队列中，得到：

• 乘以 2 的队列：4， 6， 8
• 乘以 3 的队列：6，9， 12
• 乘以 5 的队列：5， 10， 15， 20

如此循环，直到找到第 N 个丑数。

具体解法如下：

int GetUglyNumber_Solution(int index) {
    vector<int> numbers;
    numbers.push_back(1);

    queue<int> queue_2, queue_3, queue_5;
    queue_2.push(2);
    queue_3.push(3);
    queue_5.push(5);

    while (numbers.size() < index) {
    int multi_2 = queue_2.front();
    int multi_3 = queue_3.front();
    int multi_5 = queue_5.front();

    int min = multi_2;
    if (multi_3 < min || multi_5 < min) {
    min = multi_3 > multi_5 ? multi_5 : multi_3;
    }

    if (multi_2 == min) queue_2.pop();
    if (multi_3 == min) queue_3.pop();
    if (multi_5 == min) queue_5.pop();

    numbers.push_back(min);
    queue_2.push(2 * min);
    queue_3.push(3 * min);
    queue_5.push(5 * min);
    }

    return numbers[index - 1];
}