题目

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

  1. Input: n = 10
  2. Output: 12
  3. 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.

题意

找到第n个因数只有2、3、5的整数。

思路

  1. 自底向上生成第n个丑陋数：每个丑陋数都可以由之前的某一个丑陋数乘2或3或5得到。因此记录下2、3、5要乘的下一个丑陋数的下标，每一次从得到的三个数中选取最小的一个作为新的丑陋数加入列表中，并根据这个值将2、3、5要乘的下一个下标往后挪一位。如下图示例：

image.png

  1. 堆：用小顶堆存储丑陋数，每次取堆顶的数x作为最新的丑陋数，并将所有与x相同的数除去，最后再往堆里存入2x、3x、5x。重复操作n次后得到的就是第n个丑陋数。(注意这种方法每次都是用最新的丑陋数去乘2、3、5，因此可能出现int越界的情况，所以堆必须用long)

代码实现

Java

迭代

  1. class Solution {
  2.     public int nthUglyNumber(int n) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         int times2pos = 0, times3pos = 0, times5pos = 0;
  6.         while (list.size() < n) {
  7.             int times2 = list.get(times2pos) * 2;
  8.             int times3 = list.get(times3pos) * 3;
  9.             int times5 = list.get(times5pos) * 5;
  10.             int min = Math.min(Math.min(times2, times3), times5);
  11.             if (min == times2) times2pos++;
  12.             if (min == times3) times3pos++;
  13.             if (min == times5) times5pos++;
  14.             list.add(min);
  15.         }
  16.         return list.get(list.size() - 1);
  17.     }
  18. }

堆

  1. class Solution {
  2.     public int nthUglyNumber(int n) {
  3.         Queue<Long> heap = new PriorityQueue<>();
  4.         heap.offer(1l);
  5.         int count = 0;
  6.         long ans = 0;
  7.         while (count != n) {
  8.             ans = heap.poll();
  9.             while (!heap.isEmpty() && heap.peek() == ans) {
  10.                 heap.poll();
  11.             }
  12.             heap.offer(ans * 2);
  13.             heap.offer(ans * 3);
  14.             heap.offer(ans * 5);
  15.             count++;
  16.         }
  17.         return (int)ans;
  18.     }
  19. }

JavaScript

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var nthUglyNumber = function (n) {
  6.   let list = [1]
  7.   let pos2 = 0, pos3 = 0, pos5 = 0
  8.   while (list.length < n) {
  9.     let times2 = list[pos2] * 2
  10.     let times3 = list[pos3] * 3
  11.     let times5 = list[pos5] * 5
  12.     let min = Math.min(times2, times3, times5)
  13.     if (min === times2) pos2++
  14.     if (min === times3) pos3++
  15.     if (min === times5) pos5++
  16.     list.push(min)
  17.   }
  18.   return list[n - 1]
  19. }

参考

[LeetCode] 264. Ugly Number II 丑陋数之二