首页 > 其他分享 >LeetCode: 264. Ugly Number II

LeetCode: 264. Ugly Number II

时间:2022-12-05 18:02:18浏览次数:43  
标签:ugly2 ugly3 Number back II Ugly second uglyNumbers first


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:

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.

解题思路

每个 ugly number 乘以 2,3,5 之后还是 ugly number, ​​1​​ 是 ugly number

AC 代码

class Solution {
public:
int nthUglyNumber(int n) {
vector<int> uglyNumbers{1};
pair<int, int> ugly2{0, 2}, ugly3{0, 3}, ugly5{0, 5};
int cnt = 1;
while(cnt < n)
{
if(ugly2.second <= ugly3.second && ugly2.second <= ugly5.second)
{
uglyNumbers.push_back(ugly2.second);
}
else if(ugly3.second <= ugly2.second && ugly3.second <= ugly5.second)
{
uglyNumbers.push_back(ugly3.second);
}
else
{
uglyNumbers.push_back(ugly5.second);
}

if(ugly2.second == uglyNumbers.back())
{
++ugly2.first;
ugly2.second = uglyNumbers[ugly2.first]*2;
}
if(ugly3.second == uglyNumbers.back())
{
++ugly3.first;
ugly3.second = uglyNumbers[ugly3.first]*3;
}
if(ugly5.second == uglyNumbers.back())
{
++ugly5.first;
ugly5.second = uglyNumbers[ugly5.first]*5;
}
++cnt;
}

return uglyNumbers.back();
}
};


标签:ugly2,ugly3,Number,back,II,Ugly,second,uglyNumbers,first
From: https://blog.51cto.com/u_15903085/5913214

相关文章