My Java O(n) implementation and explaination.


  • 1
    C

    Use three "Pointers" idx2, idx3, idx5 to indicate the multiplications of previous ugly numbers of 2, 3, and 5, respectively. So we only need to keep one result list. Any time a multiplication factor or 2, 3, or 5 is chosen, the respective index moves forward. Duplicate answers will be skipped. Until we got nth answer.

    public int nthUglyNumber(int n) {
        List<Integer> results = new ArrayList<>();
        results.add(1);
        int idx2 = 0;
        int idx3 = 0;
        int idx5 = 0;
        int totalNums= 1;
        while(totalNums < n ){
            int val2 = results.get(idx2) * 2;
            int val3 = results.get(idx3) * 3;
            int val5 = results.get(idx5) * 5;
            int thisPick;
            if(val2 <= val3 && val2 <= val5){
                thisPick = val2;
                idx2++;
            } else if(val3 <= val2 && val3 <= val5){
                thisPick = val3;
                idx3++;
            } else {  // (val5 <= val2 && val5 <= val3)
                thisPick = val5;
                idx5++;
            }
            if(results.get(totalNums-1) != thisPick) {
                results.add(thisPick);
                totalNums++;
            }
        }
        return results.get(n - 1);
    }

  • 0
    C
    This post is deleted!

Log in to reply
 

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