categories: leetcode

carbon.png

题目描述

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

  1.  is the sequence of the first

10

  1.  ugly numbers.**Note: ** 
  3. 1. `1` is typically treated as an ugly number.
  4. 1. `n` **does not exceed 1690**.
  5. <a name="36967e2c"></a>
  6. ## 参考代码
  8. ```java
  9. class Solution {
  10.     public int nthUglyNumber(int n) {
  11.         int factors[] = {2,3,5};
  12.         //优先队列
  13.         Queue<Long> queue = new PriorityQueue<>();
  14.         queue.offer(1L);
  15.         注意第1690个可能会超过int的范围
  16.         while (true) {
  17.             long min = queue.poll();//每次取最小值相乘，取得第n个数
  18.             if (n == 1) {
  19.                 return (int)min;
  20.             }
  21.             for (int i = 0; i < 3; i++) {
  22.                 long ugly = factors[i] * min;
  23.                 if(!queue.contains(ugly)) {//去重
  24.                     queue.offer(ugly);
  25.                 }
  26.             }
  27.             n--;
  28.         }
  29.     }
  30. }

思路及总结

利用优先队列进行排序，然后将2、3、5中最小值作为下次相乘的因子，确保没有重复的数字，queue.poll()取得的是即是第 1\2\3\4\5。。。 个数,当n = 1 时，min即是第n个数.

参考

https://chuansongme.com/n/1648591652025