LeetCode 0264 - Ugly Number II

Reck Zhang

发布于 2021-08-11 11:46:44

1940

发布于 2021-08-11 11:46:44

文章被收录于专栏：Reck Zhang

Ugly Number II

Desicription

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 is typically treated as an ugly number.
n does not exceed 1690.

Solution

class Solution {
public:
    long long nthUglyNumber(int n) {
        set<long long> ugly_number;
        ugly_number.insert(1);
        while(n--) {
            if(!n) {
                return *ugly_number.begin();
            }
            const auto& top = ugly_number.begin();
            ugly_number.insert(*top * 2);
            ugly_number.insert(*top * 3);
            ugly_number.insert(*top * 5);
            ugly_number.erase(top);
        }
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-12-12，如有侵权请联系 cloudcommunity@tencent.com 删除

include