- 优先队列
维护一个优先队列。先取出最小的数字，将其乘以2、3、5，如果发现没有重复的话就装入优先队列中，需要用到set进行去重。
class Solution {
public int nthUglyNumber(int n) {
Set<Long> set = new HashSet<>();
PriorityQueue<Long> queue = new PriorityQueue<>();
long res = 0, arr[] = new long[]{2, 3, 5};
queue.offer(1L);
set.add(1L);
for(int i = 0; i < n; i++){
res = queue.poll();
for(long val : arr){
if(set.add(res*val)) queue.offer(res*val);
}
}
return (int)res;
}
}
- dp
维护一个dp数组和三个指针，分别代表2、3、5的当前位置。最新的值为2、3、5指针指向的数乘以相应的常数，取最小值。
然后对如果最新的值等于该指针乘以常数的话，就将该指针移动相应位置。（注意，一轮下来可能移动多个指针，这是因为三个指针得到的数字可能相等）
class Solution {
public int nthUglyNumber(int n) {
int arr[] = new int[n], i2 = 0, i3 = 0, i5 = 0;
arr[0] = 1;
for(int i = 1; i < n; i++){
arr[i] = Math.min(arr[i2]*2, Math.min(arr[i3]*3, arr[i5]*5));
if(arr[i] == arr[i2]*2) i2++;
if(arr[i] == arr[i3]*3) i3++;
if(arr[i] == arr[i5]*5) i5++;
}
return arr[n-1];
}
}