剑指 Offer 49. 丑数

剑指 Offer 49. 丑数

难度：

      m
     
     
      i
     
     
      d
     
     
      d
     
     
      l
     
     
      e
     
    
   
  
  
   \color{orange}{middle}
  
 
middle

题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

1.                                1                              1                  1 是丑数。
   

2.                                n                              n                  n**不超过** 1690。
   

注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/

算法

(三指针)

依次枚举所有的丑数，然后求出其中的第 n 个丑数。

复杂度分析

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度 : O ( n ) O(n) O(n)

C++ 代码

class Solution {
public:intnthUglyNumber(int n){
        vector<int>q(1,1);int i =0, j =0, k =0;while(--n){int t =min(q[i]*2,min(q[j]*3, q[k]*5));
            q.push_back(t);if(q[i]*2== t ) i++;if(q[j]*3== t ) j++;if(q[k]*5== t ) k++;}return q.back();}};