Ex49 丑数

题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

解题思路

把一个数作为起始值，下一个数就是：min(vec[index2]*2, vec[index3]*3, vec[index5]*5)。如果哪个乘数下的index是min值，就更新相应的index。

是有一点动态规划的思想在里面的。

代码

class Solution {
 public:
  int nthUglyNumber(int n) {
    int start = 1;
    std::vector<int> vec;
    vec.reserve(n);
    vec.push_back(start);
    int index2 = 0, index3 = 0, index5 = 0;
    for (int i = 1; i < n; ++i) {
      int res =
          std::min(std::min(vec[index2] * 2, vec[index3] * 3), vec[index5] * 5);
      vec.push_back(res);
      if (res == vec[index2] * 2) ++index2;
      if (res == vec[index3] * 3) ++index3;
      if (res == vec[index5] * 5) ++index5;
    }
    return *(vec.end() - 1);
  }
};

结果

执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了45.28%的用户

内存消耗：7.9 MB, 在所有 C++ 提交中击败了33.06%的用户