[刷题防痴呆] 0264 - 丑数 II (Ugly Numbe

题目地址

https://leetcode.com/problems/ugly-number-ii/description/

题目描述

264. Ugly Number II

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 is typically treated as an ugly number.
n does not exceed 1690.

思路

• heap + hashset.
• 将2, 3, 5, 放入.
• 然后不停往后计算. 乘以2, 3, 5. 用hashset判重.

关键点

• 中间可能会溢出, 用long.
• long to int: number.intValue().
• int to long: Long.valueOf(2).

代码

• 语言支持：Java

class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> pq = new PriorityQueue<>();
        Set<Long> set = new HashSet<>();
        
        List<Long> primes = new ArrayList<>();
        primes.add(Long.valueOf(2));
        primes.add(Long.valueOf(3));
        primes.add(Long.valueOf(5));
        
        for (int i = 0; i < 3; i++) {
            pq.offer(primes.get(i));
            set.add(primes.get(i));
        }
        
        Long number = Long.valueOf(1);
        for (int i = 1; i < n; i++) {
            number = pq.poll();
            for (int j = 0; j < 3; j++) {
                long temp = primes.get(j) * number;
                if (!set.contains(temp)) {
                    pq.offer(temp);
                    set.add(temp);
                }
            }
        }
        
        return number.intValue();
    }
}