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();
   }
};