C solution with O(n) time


  • 1
    P
    int nthUglyNumber(int n) {
        int* lists;
        lists = malloc(sizeof(int) * n);
        int a,b,c;
        a = b = c = 0;
        lists[0] = 1;
        int tempa, tempb, tempc;
        for(int i = 1; i < n; i ++){
            tempa = lists[a] * 2;
            tempb = lists[b] * 3;
            tempc = lists[c] * 5;
            if(tempa < tempb){
                if(tempa < tempc){
                    lists[i] = tempa;
                    a ++;
                }else if(tempa > tempc){
                    lists[i] = tempc; 
                    c ++;
                }else{
                    lists[i] = tempc; 
                    a ++;
                    c ++;
                }
            }else if(tempa > tempb){
                if(tempb < tempc){
                    lists[i] = tempb; 
                    b ++;
                }else if(tempb > tempc){
                    lists[i] = tempc; 
                    c ++;
                }else{
                    lists[i] = tempc; 
                    b ++;
                    c ++;
                }
            }else{
                if(tempc > tempa){
                    lists[i] = tempb; 
                    a ++;
                    b ++;
                }else if(tempc < tempa){
                    lists[i] = tempc; 
                    c ++;
                }else{
                    lists[i] = tempc; 
                    a ++;
                    b ++;
                    c ++;
                }
            }
        }
        return lists[n - 1];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.