Simple java solution with explanation


  • 0
    H
    public int nthUglyNumber(int n) {
        // 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20.... is the sequence of the ugly numbers
        // 2, 3, 2*2, 5, 2*3, 3*3, 2*5, 3*5 
        // 2^a 3^b 5^c
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return a - b;
            }
        });
        for (int i = -1; i * i <= n; i++) {
            for (int j = -1; j * j <= n; j++) {
                for (int k = -1; k * k <= n; k++) {
                    pq.add((int)(Math.pow(5, i + 1)*Math.pow(3, j + 1)*Math.pow(2, k + 1)));
                }
            }
        }
        int res = 1;
        for (int i = 0; i < n; i++) {
            res = pq.poll();
        }
        return res;
    }
    

    idea: every ugly number is comprised of multiple 2, times multiple 3, and multiple 5. That is ugly number = Math.pow(2, x)*Math.pow(3, y)*Math.pow(5, z). Consider the method of counting the primes. I use sqrt() here to reduce the useless calculation. Meantime, I use the heap to get the nth element.


Log in to reply
 

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