Ugly Number

发布于 2025-02-22 13:01:26 字数 4526 浏览 0 评论 0 收藏 0

Source

leetcode: Ugly Number | LeetCode OJ
lintcode: (4) Ugly Number

Ugly number is a number that only have factors 3, 5 and 7.

Design an algorithm to find the Kth ugly number.
The first 5 ugly numbers are 3, 5, 7, 9, 15 ...

Example
If K=4, return 9.
Challenge
O(K log K) or O(K) time.

题解 1 - TLE

Lintcode 和 Leetcode 中质数稍微有点区别，这里以 Lintcode 上的版本为例进行说明。寻找第 K 个丑数，丑数在这里的定义是仅能被 3，5，7 整除。简单粗暴的方法就是挨个检查正整数，数到第 K 个丑数时即停止。

Java

class Solution {
  /**
   * @param k: The number k.
   * @return: The kth prime number as description.
   */
  public long kthPrimeNumber(int k) {
    if (k <= 0) return -1;

    int count = 0;
    long num = 1;
    while (count < k) {
      num++;
      if (isUgly(num)) {
        count++;
      }
    }

    return num;
  }

  private boolean isUgly(long num) {
    while (num % 3 == 0) {
      num /= 3;
    }
    while (num % 5 == 0) {
      num /= 5;
    }
    while (num % 7 == 0) {
      num /= 7;
    }

    return num == 1;
  }
}

源码分析

判断丑数时依次约掉质因数 3，5，7，若处理完所有质因数 3,5,7 后不为 1 则不是丑数。自增 num 时应在判断是否为丑数之前。

复杂度分析

无法准确分析，但是估计在 O(n3)O(n^3)O(n3) 以上。

题解 2 - 二分查找

根据丑数的定义，它的质因数只含有 3, 5, 7, 那么根据这一点其实可以知道后面的丑数一定可以从前面的丑数乘 3,5,7 得到。那么可不可以将其递推关系用数学公式表示出来呢？

我大概做了下尝试，首先根据丑数的定义可以写成 Uk=3x3⋅5x5⋅7x7U_k = 3^{x_3} \cdot 5^{x_5} \cdot 7^{x_7}Uk=3x3⋅5x5⋅7x7, 那么 Uk+1U_{k+1}Uk+1 和 UkU_kUk 的不同则在于 x3,x5,x7x_3, x_5, x_7x3,x5,x7 的不同，递推关系为 Uk+1=Uk⋅3y3⋅5y5⋅7y73z3⋅5z5⋅7z7U_{k+1} = U_k \cdot \frac{3^{y_3} \cdot 5^{y_5} \cdot 7^{y_7}}{3^{z_3} \cdot 5^{z_5} \cdot 7^{z_7}}Uk+1=Uk⋅3z3⋅5z5⋅7z73y3⋅5y5⋅7y7,将这些分数按照从小到大的顺序排列可在 O(K)O(K)O(K) 的时间内解决，但是问题来了，得到这些具体的 y,zy, zy,z 就需要费不少时间，且人工操作极易漏解。:( 所以这种解法只具有数学意义，没有想到好的实现方法。

除了这种找相邻递推关系的方法我们还可以尝试对前面的丑数依次乘 3, 5, 7，直至找到比当前最大的丑数大的一个数，对乘积后的三种不同结果取最小值即可得下一个最大的丑数。这种方法需要保存之前的 N 个丑数，由于已按顺序排好，天然的二分法。

C++

class Solution {
public:
  /*
   * @param k: The number k.
   * @return: The kth prime number as description.
   */
  long long kthPrimeNumber(int k) {
    if (k <= 0) return -1;

    vector<long long> ugly(k + 1);
    ugly[0] = 1;
    int index = 0, index3 = 0, index5 = 0, index7 = 0;
    while (index <= k) {
      long long val = ugly[index3]*3 < ugly[index5]*5 ? ugly[index3]*3 : ugly[index5]*5;
      val = val < ugly[index7]*7 ? val : ugly[index7]*7;
      if (val == ugly[index3]*3) ++index3;
      if (val == ugly[index5]*5) ++index5;
      if (val == ugly[index7]*7) ++index7;
      ugly[++index] = val;
    }
    return ugly[k];
  }
};

Java

class Solution {
  /**
   * @param k: The number k.
   * @return: The kth prime number as description.
   */
  public long kthPrimeNumber(int k) {
    if (k <= 0) return -1;

    ArrayList<Long> nums = new ArrayList<Long>();
    nums.add(1L);
    for (int i = 0; i < k; i++) {
      long minNextUgly = Math.min(nextUgly(nums, 3), nextUgly(nums, 5));
      minNextUgly = Math.min(minNextUgly, nextUgly(nums, 7));
      nums.add(minNextUgly);
    }

    return nums.get(nums.size() - 1);
  }

  private long nextUgly(ArrayList<Long> nums, int factor) {
    int size = nums.size();
    int start = 0, end = size - 1;
    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (nums.get(mid) * factor > nums.get(size - 1)) {
        end = mid;
      } else {
        start = mid;
      }
    }
    if (nums.get(start) * factor > nums.get(size - 1)) {
      return nums.get(start) * factor;
    }

    return nums.get(end) * factor;
  }
}