0%

丑数

发表于 更新于

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

类质数筛法

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
class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if (index <= 0)
        {
            return 0;
        }
        else
        {
            vector<int> numbers = {1};
            int i2 = 0, i3 = 0, i5 = 0;
            while (numbers.size() < index)
            {
                int max_number = min({numbers[i2] * 2, numbers[i3] * 3, numbers[i5] * 5});
                numbers.push_back(max_number);
                while (numbers[i2] * 2 <= max_number)
                {
                    i2++;
                }
                while (numbers[i3] * 3 <= max_number)
                {
                    i3++;
                }
                while (numbers[i5] * 5 <= max_number)
                {
                    i5++;
                }
            }
            return *numbers.rbegin();
        }
    }
};