本文共 1155 字，大约阅读时间需要 3 分钟。

为了解决丑数问题，我们可以使用三指针法，高效地找到第n个丑数。丑数是2、3和5的幂次乘积，因此可以通过归并排序的方式，逐步生成最小的丑数。

方法思路

丑数可以看作三个等差数列（被2、3、5分别整除的数）的并集。为了生成丑数，我们可以使用一个贪心算法，每次取三个数列中最小的数，并将其加入结果集中。具体步骤如下：

这种方法的时间复杂度是O(n)，因为每次循环只需比较三个数，较为高效。

解决代码

#include 
   
    #include 
    
     class Solution {    std::vector
     
       q;    int i = 0, j = 0, k = 0;        public:        int getUglyNumber(int n) {            q.push_back(1); // 初始丑数是1            while (q.size() < n) {                int t1 = q[i] * 2;                int t2 = q[j] * 3;                int t3 = q[k] * 5;                int t = std::min(t1, t2, t3);                q.push_back(t);                if (t == t1) {                    i++;                } else if (t == t2) {                    j++;                } else if (t == t3) {                    k++;                }            }            return q.back();        }};
     
    
   

代码解释

这种方法确保了我们能够在最少的操作次数内找到第n个丑数，非常高效且直接。