丑数II

来自Leetcode第264题丑数II

编写一个程序，找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

---

堆

来自官方题解

从堆中包含一个数字开始：1，去计算下一个丑数。将 1 从堆中弹出然后将三个数字添加到堆中：1 * 2，1 * 3和 1 * 5。

现在堆中最小的数字是 2。为了计算下一个丑数，要将 2 从堆中弹出然后添加三个数字：2×2, 2×3，和 2×5。

重复该步骤计算所有丑数。在每个步骤中，弹出堆中最小的丑数 kk，并在堆中添加三个丑数：k×2, k×3，和 k×5。

• 初始化预计算用到的数组 nums，堆 heap 和哈希表 seen 跟踪在堆中出现过的元素，避免重复。
  • 循环计算丑数，每个步骤：
    • 弹出堆中最小的数字 k 并添加到数组 nums 中。
    • 若 2k，3k，5k 不存在在哈希表中，则将其添加到栈中并更新哈希表。
• 返回在数组中预先计算好的丑数。

class Ugly {
  public int[] nums = new int[1690];
  Ugly() {
    HashSet<Long> seen = new HashSet();
    PriorityQueue<Long> heap = new PriorityQueue<Long>();
    seen.add(1L);
    heap.add(1L);

    long currUgly, newUgly;
    int[] primes = new int[]{2, 3, 5};
    for(int i = 0; i < 1690; ++i) {
      currUgly = heap.poll();
      nums[i] = (int)currUgly;
      for(int j : primes) {
        newUgly = currUgly * j;
        if (!seen.contains(newUgly)) {
          seen.add(newUgly);
          heap.add(newUgly);
        }
      }
    }
  }
}

class Solution {
  public static Ugly u = new Ugly();
  public int nthUglyNumber(int n) {
    return u.nums[n - 1];
  }
}

三指针

从数组中只包含一个丑数数字 1 开始，使用三个指针 i_2i2, i_3i3 和 i_5i5，标记所指向丑数要乘以的因子。

算法很简单：在 $2 \times \textrm{nums}[i_2]，3 \times \textrm{nums}[i_3] 和 5 \times \textrm{nums}[i_5]$ 选出最小的丑数并添加到数组中。并将该丑数对应的因子指针往前走一步。重复该步骤直到计算完 1690 个丑数。

class Ugly {
  public int[] nums = new int[1690];
  Ugly() {
    nums[0] = 1;
    int ugly, i2 = 0, i3 = 0, i5 = 0;

    for(int i = 1; i < 1690; ++i) {
      ugly = Math.min(Math.min(nums[i2] * 2, nums[i3] * 3), nums[i5] * 5);
      nums[i] = ugly;

      if (ugly == nums[i2] * 2) ++i2;
      if (ugly == nums[i3] * 3) ++i3;
      if (ugly == nums[i5] * 5) ++i5;
    }
  }
}

class Solution {
  public static Ugly u = new Ugly();
  public int nthUglyNumber(int n) {
    return u.nums[n - 1];
  }
}