Java solution with three queues


  • 5
    A

    I saw this on CC150. The idea is to use three queues to store three multiples of each ugly number. Have to use long instead of int to avoid overflow.

    public class Solution {
        public int nthUglyNumber(int n) {
            if (n < 1) return 0;
            Queue<Long> queue2 = new LinkedList<>();
            Queue<Long> queue3 = new LinkedList<>();
            Queue<Long> queue5 = new LinkedList<>();
            queue2.add(1l);
            long val = 0;
            for (int i = 0; i < n; i++) {
                long v2 = queue2.isEmpty() ? Long.MAX_VALUE : queue2.peek();
                long v3 = queue3.isEmpty() ? Long.MAX_VALUE : queue3.peek();
                long v5 = queue5.isEmpty() ? Long.MAX_VALUE : queue5.peek();
                val = Math.min(v2, Math.min(v3, v5));
                if (val == v2) {
                    queue2.poll();
                    queue2.add(val*2);
                    queue3.add(val*3);
                }
                else if (val == v3) {
                    queue3.poll();
                    queue3.add(val*3);
                }
                else
                    queue5.poll();
                queue5.add(val*5);
            }
            return (int)val;
        }
    }

Log in to reply
 

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