264. Ugly Number II --------M

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 the first 10 ugly numbers.

Note:  

1. 1 is typically treated as an ugly number.
2. n does not exceed 1690.

A:

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> V{1,2,3,4,5};
        int i2=0,i3=0,i5=0;
        while(V.size()<n){
            int last = V.back();
            while(V[i2] * 2 <= last){
                i2++;
            }
            while(V[i3] * 3 <= last){
                i3++;
            }
            while(V[i5] * 5 <= last){
                i5++;
            }
            V.push_back(min( min(V[i2]*2, V[i3]*3), V[i5]*5));
        }
        return V[n-1];
    }
};

就是用最小堆保存已经发现了的数字的可能2,3,5乘积。

import java.util.*;
public class Solution {
    public int nthUglyNumber(int n) {
        Queue<Integer> queue = new PriorityQueue(3*n,new Comparator<Integer>(){
            public int compare(Integer a,Integer b){
                return a-b;
            }
        });
        Set<Integer> found = new HashSet<Integer>();
        queue.offer(1);
        found.add(1);
        for(int i =0;i<n-1;i++){
            int val = queue.poll();
            if(val <= Integer.MAX_VALUE/2)
                helper(found,2*val,queue);
            if(val <= Integer.MAX_VALUE/3)
                helper(found,3*val,queue);
            if(val <= Integer.MAX_VALUE/5)
                helper(found,5*val,queue);
        }
        return queue.poll();
    }
    private void helper(Set<Integer> set, int val,Queue<Integer> queue){
        if(!set.contains(val))
            queue.offer(val);
        set.add(val);
    }
}

Mistakes:

1： 最小堆的声明
2： 可能有重复，因此需要一个Set
3:   int 类型，终极计算过程，可能有溢出