丑数

丑数

题目描述

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

思路: 当前丑数之前的某个数乘以2后小于当前丑数, 这个数之后的所有丑数乘以2后都大于当前丑数, 同理, 对因子3和5都用这个方法, 找出三个因子对应的位置, 并保存用于下次循环

class Solution {
public:
    int minNumber(int n1, int n2, int n3) {
        return ((n1 < n2 ? n1 : n2) < n3 ? (n1 < n2 ? n1 : n2) : n3);
    }
    
    int GetUglyNumber_Solution(int index) {
        if(0 >= index) {
            return 0;
        }
        vector<int> vt;
        vt.push_back(1);
        //int pN = 0;
        int pN2 = 0;
        int pN3 = 0;
        int pN5 = 0;
        
        while (vt.size() < index) {
            int min = minNumber(vt[pN2] * 2, vt[pN3] * 3, vt[pN5] * 5);
            vt.push_back(min);
            while (vt[pN2] * 2 <= min) {
                pN2++;
            }
            while (vt[pN3] * 3 <= min) {
                pN3++;
            }
            while (vt[pN5] * 5 <= min) {
                pN5++;
            }
        }
        return vt.back();
    }
};

暴力法, 把从1到n的所有数字全都判断一次, 牛客提交没通过, 可能超时了

class Solution {
public:
    
    bool isUglyNumber(int number) {
        while (number % 2 == 0) {
            number /= 2;
        }
        while (number % 3 == 0) {
            number /= 3;
        }
        while (number % 5 == 0) {
            number /= 5;
        }

        return (number == 1) ? true : false;
    }
    
    int GetUglyNumber_Solution(int index) {
        if (0 >= index) {
            return 0;
        }
        
        int number = 0;
        int uglyFound = 0;
        
        while (uglyFound < index) {
            number++;
            if (isUglyNumber(number)) {
                uglyFound++;
            }
        }
        return number;
    }
};