Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example: Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of
Method - 1
class Solution { // keypoint: How to get exactly nth number // Solution: minHeap // O(nlogn) public int nthUglyNumber(int n) { if(n <= 0){ return -1;} if(n == 1){ return 1;} PriorityQueue<Long> minHeap = new PriorityQueue<>(); minHeap.offer(1L); for(int i = 1; i < n; i++){ long tmp = minHeap.poll(); while(!minHeap.isEmpty() && tmp == minHeap.peek()){ //remove the duplicate ones minHeap.poll(); } minHeap.offer(tmp * 2); // **** tmp **** minHeap.offer(tmp * 3); minHeap.offer(tmp * 5); } return (int)(long) minHeap.poll(); }Method-2
/* The key point is the all ugly can be divided to 2, 3 and 5, so we can separate to three groups as below {1 *2, 2 *2, 3 *2 ...} {1 *3, 2 *3, 3 *3 ...} {1 *5, 2 *5, 3 *5 ...} */ // Solution: Iteration // O(n) // 14 is not a ugly number since its prime factor includes 7 public int nthUglyNumber(int n) { if (n <= 0) { return -1;} if (n == 1) { return 1;} int[] nth = new int[n]; int index2 = 1, index3 = 1, index5 = 1; int factor2 = 2, factor3 = 3, factor5 = 5; nth[0] = 1; for (int i = 1; i < n; i++) { int min = Math.min(factor2, Math.min(factor3, factor5)); nth[i] = min; if (min == factor2) { factor2 = nth[index2++] * 2; } if (min == factor3) { factor3 = nth[index3++] * 3; } if (min == factor5) { factor5 = nth[index5++] * 5; } } return nth[n - 1]; }