LeetCode: 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.

Example:

1
2
3
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.

所有的ugly number必然由已有的ugly number乘以2、3、5获得，所以我们需要使用三个index，分别作为乘以2、3、5后最有可能成为下一个ugly number的数字的位置，并且进行比较。如果说它真的成为了下一个ugly number，那么就把它的索引加一后继续寻找下下个ugly number。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> lists = {1};
        int index2 = 0, index3 = 0, index5 = 0;
        while (--n) {
            int newNum = min(lists[index2] * 2, lists[index3] * 3);
            newNum = min(newNum, lists[index5] * 5);
            lists.push_back(newNum);
            if (newNum == lists[index2] * 2)
                index2++;
            if (newNum == lists[index3] * 3)
                index3++;
            if (newNum == lists[index5] * 5)
                index5++;
        }
        return lists[lists.size()-1];
    }
};