计算丑数算法

Question

丑数是指只包含质因数 2、3、5 的正整数。例如，前几个丑数是 1、2、3、4、5、6、8、9、10、12 等。 一个常见的解决方法是使用动态规划。假设我们已经找到了前 n 个丑数，然后我们从这些丑数中找出一个最小的丑数 u。那么下一个丑数一定是 u * 2、u * 3 或 u * 5 中的一个，因为前面的丑数已经是按照从小到大的顺序排列的。我们可以分别计算出 u * 2、u * 3、u * 5 并取最小值，然后将它加入到已知的丑数序列中。

以下是一个动态规划的实现代码：

def uglyNumber(n): if n <= 0: return 0 ugly_numbers = [1] p2, p3, p5 = 0, 0, 0

for i in range(1, n):
    ugly_num = min(ugly_numbers[p2] * 2, ugly_numbers[p3] * 3, ugly_numbers[p5] * 5)
    ugly_numbers.append(ugly_num)

    while ugly_numbers[p2] * 2 <= ugly_num:
        p2 += 1
    while ugly_numbers[p3] * 3 <= ugly_num:
        p3 += 1
    while ugly_numbers[p5] * 5 <= ugly_num:
        p5 += 1

return ugly_numbers[n - 1]

在主函数中调用 uglyNumber(n) 即可计算出第 n 个丑数。

---

每一次只增加 一个 最小的数

public class Solution {
  final int d[] = { 2, 3, 5 };
  public int GetUglyNumber_Solution(int index) {
    if(index == 0) return 0;
    int a[] = new int[index];
    a[0] = 1;
    int p[] = new int[] { 0, 0, 0 };
    int num[] = new int[] { 2, 3, 5 };
    int cur = 1;
    while (cur < index) {
      int m = finMin(num[0], num[1], num[2]);
      if (a[cur - 1] < num[m])
        a[cur++] = num[m];
      p[m] += 1;
      num[m] = a[p[m]] * d[m];
    }
    return a[index - 1];
  }
  private int finMin(int num2, int num3, int num5) {
    int min = Math.min(num2, Math.min(num3, num5));
    return min == num2 ? 0 : min == num3 ? 1 : 2;
  }
}