Ugly number is a number that only have factors 2, 3 and 5.

Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

Note that 1 is typically treated as an ugly number.

版本1

思路:依次比对每个整数,直到找出第n个满足条件的值

int isungly(int n) {
        if (n == 1) return 1;
        
        if (n%2 == 0) {
            return isungly(n/2);
        }
        
        if (n%3 == 0) {
            return isungly(n/3);
        }
        
        if (n%5==0) {
            return isungly(n/5);
        }
        
        return 0;
    }
    

    /**
     * @param n: An integer
     * @return: the nth prime number as description.
     */
    int nthUglyNumber(int n) {
        // write your code here
        
        int ret = 0;
        int i = 0;
        while (n > 0) {
            i++;
            
            //Note that 1 is typically treated as an ugly number
            if (i == 1) {
                ret = 1;
                n--;
                continue;
            }
            
            
            if (isungly(i)) {
                ret = i;
                n--;
            }
        }
        return ret;
    }

PS: 该算法会耗费大量的时间,而且越大的值将需要花费更大的时间

版本2

思路:针对版本1进行了优化,若是偶数,只要判断该偶数的一半是否满足条件,满足则其也满足,不满足则其也不满足,若被3整除,则查看其值是否是上一次被3整除而符号条件的值,若被5整除,则比较除5后是否等于之前的值

long long gcache[10000000] = {0};
int gj2 = 0;
int gj3 = 0;
int gj5 = 0;

int isugly(long long digit, int j) {
    if (digit == 1) {
        return 1;
    }

    if (digit%2 == 0) {
        long long tmp = digit/2;
        if (tmp == gcache[gj2]) {
            gj2++;
            return 1;
        } else {
            return 0;
        }
    } else if (digit%5 == 0) {
        long long tmp = digit/5;

        if (tmp == gcache[gj5]) {
            while (gcache[++gj5]%2 == 0);
            return 1;
        } else {
            return 0;
        }
    } else if (digit%3 == 0) {
        long long tmp = digit/3;

        if (tmp == gcache[gj3]) {
            gj3=j;
            return 1;
        } else {
            return 0;
        }
    }
    return 0;
}

int nthUglyNumber(int n) {
    int ret = 0;
    long long i = 0;
    int j = 0;
    while (n > 0) {
        i++;

        if (isugly(i, j)) {
            n--;
            ret = i;
            gcache[j++] = i;
        }

    }
    return ret;
}

版本3

思路:不采用遍历整数方式,直接通过已满足的值进行计算,并按大小顺序插入

long long gcache1[10000000] = {1};

int nthUglyNumber(int n) {

    int i = 0;
    int i2 = 0;
    int i3 = 0;
    int i5 = 0;
    long long v2 = gcache1[i2]*2;
    long long v3 = gcache1[i3]*3;
    long long v5 = gcache1[i5]*5;

    //already insert 1
    n--;
    
    while (n > 0) {
        n--;

        //insert min value
        if (v2 < v3 && v2 < v5) {
            gcache1[++i] = v2;
            i2++;
            v2 = gcache1[i2]*2;
        } else if (v3 < v2 && v3 < v5) {
            gcache1[++i] = v3;
            i3++;
            while(gcache1[i3]%2 == 0||((v3 = gcache1[i3]*3) == v5)) {
                i3++;
            }
        } else if (v5 < v2 && v5 < v3) {
            gcache1[++i] = v5;
            i5++;
            while(gcache1[i5]%2 == 0||((v5 = gcache1[i5]*5) == v3)) {
                i5++;
            }
        }
    }
    return gcache1[i];
}