丑数题解

分手后的思念是犯贱 2022-05-19 10:39 163阅读 0赞

#### 写在前面 ####

> 剑指offer 编程题：丑数。

##### 参考目录 #####

##### 题目描述 #####

*  把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

> 基本思路（暴力解）

*  从2开始遍历每一个数判断是不是丑数。如果是丑数计数器count++，如果不是数字加1，继续判断。算法复杂度极大。

> 进阶思路

*  观察发现，每一个丑数本身必然是之前的某个丑数的值乘以2或3或5。我们只需要按照这个规律找到下一个丑数，同时确定下一个丑数是谁。简单的方式是从1开始维护一个数组，数组存放求解第N个丑数过程当中的中间结果。通过递推关系我们可以得出 :
 *  **next\[n\] = min(M2,M3,M5);**
 *  M2为遍历数组前n-1个元素乘以2得到的第一个大于next\[n-1\]的值同理可得M3，M5。  
    缺陷就是每次都需要遍历前n-1个元素得到M2,M3,M5.整个算法的复杂度为O(N\*N);

> 改进方案

其实每次在找M2，M3，M5的过程可以看成在前面的丑数当中找到某个丑数乘以2或3获刚好大于next\[n-1\]。  
假设位置i的元素是我们需要找到求得M2的数组下标。每次从头开始到i-1遍历得到的值乘以2都会小于next\[n-1\]，同时从i+1开始到n-1得到的乘积都大于next\[n\]。所以通过记录下标的方式可以不用做过多的遍历。以n2,n3,n5表示当前对于2，3，5合适的下标。初始化都为0。当求得的next\[n\]等于某个因子乘出来的积那么对应的下标加1。

> 代码

class Solution {
    public:
        int GetUglyNumber_Solution(int index) {
            if(index<=0) return 0;
            if(index==1) return 1;
            vector<int> v;
            v.push_back(1);
            int n2=0,n3=0,n5=0;
            for(int i=0;i<index-1;++i) {
                int m2 = v[n2]*2;
                int m3 = v[n3]*3;
                int m5 = v[n5]*5;
                int tempMin = min(m2,min(m3,m5)); //竞争产生下一个丑数 （最小）
                //将产生这个丑数的index*向后挪一位；  
                if(m2==tempMin) ++n2;
                if(m3==tempMin) ++n3;//这里不能用elseif，因为可能有两个最小值，这时都要挪动
                if(m5==tempMin) ++n5; 
                v.push_back(tempMin);
            }
            return v[index-1];
        }
    };