🔗丑数

这道题看起来没有很复杂，最简单的思路当然是用哈希表来存储，看了题解以后发现最合适的方法是看作链表合并，听上去思路是豁然开朗了，但是实现起来却没有很简单直接。这里我就记录一下我实现时的一些思考。

1. 看作三个链表合并实现时不需要存储三个链表！

   如果还需要实现三个链表那根本就没有在哈希的基础上优化什么。我们来看一下这三个链表，以n=10为例：

   丑数序列：1—>2—>3—>4—>5—>6—>8—>9—>10—>12

   2乘积的序列：1—>2—>4—>6—>8—>10—>12

   3乘积的序列：1—>3—>6—>9—>12

   5乘积的序列：1—>5—>10

   当刚知道可以看作链表合并的时候，第一反应以为三个等比序列，实际上根本不是！纸上得来终觉浅，只有写出来了我们才能清楚地看到乘积的对象，所有三个链表的值都是从我们要的丑数序列中截取的部分，所以我们只需要一个丑数序列就能够实现，只要控制不同的链表对应的指针就可以了！

2. 那么我们是否一定需要一个丑数序列存储呢？

   既然我们不需要三个链表存储，那么我们是否需要把丑数序列存储下来呢？只要数到10就好了，看上去好像不需要，实际上并不可行！因为三个链表的基础就是丑数序列，为了得到被乘数我们必须把之前的丑数序列存储下来才能知道我们到底到哪了。

3. 如果遇到重复的数值呢？我们来看下题解的写法，会不会遇到重复数反复计数的情况？比如$2\times 3=3\times 2$？

   class Solution {
   public:
       int nthUglyNumber(int n) {
           vector<int> ugly(n,0);
           int p=0;
           int p2=0,p3=0,p5=0;
           int prod2=1,prod3=1,prod5=1;
           int Min=0;
           while(p<n){
               Min=min(prod2,min(prod3,prod5));
               ugly[p]=Min;
               p++;
               if(Min==prod2){
                   prod2=ugly[p2]*2;
                   p2++;
               }
               if(Min==prod3){
                   prod3=ugly[p3]*3;
                   p3++;
               }
               if(Min==prod5){
                   prod5=ugly[p5]*5;
                   p5++;
               }
           }
           return ugly[n-1];
       }
   };
   

   我们观察一下就知道，这个if不是else if，这意味着，即使有重复的情况指针也会往前走了。

4. 实现的时候要特别注意数值和指针的区别，prod2，prod3，prod5是链表的值，p2,p3,p5是它们走到哪的指针。

没想到看上去不难的实现我却纠结了这么多，现在记录下来希望对以后有帮助。