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

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

c plus

  • 动态规划

题解

  1. class Solution {
  2. public:
  3.     int nthUglyNumber(int n) {
  4.         vector<int> dp(n, 0);
  5.         dp[0] = 1;
  6.         int p2 = 0, p3 = 0, p5 = 0;//用三个快慢指针维护三个组数。
  8.         for (int i = 1; i < n; i++) {
  9.             dp[i] = min(min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5);
  10.             if (dp[i] == dp[p2] * 2)
  11.                 p2++;
  12.             if (dp[i] == dp[p3] * 3)
  13.                 p3++;
  14.             if (dp[i] == dp[p5] * 5)
  15.                 p5++;   
  16.         } 
  17.         return dp[n - 1];
  18.     }
  19. };

%E6%88%91%E4%BB%AC%E6%8A%8A%E5%8F%AA%E5%8C%85%E5%90%AB%E5%9B%A0%E5%AD%90%202%E3%80%813%20%E5%92%8C%205%20%E7%9A%84%E6%95%B0%E7%A7%B0%E4%BD%9C%E4%B8%91%E6%95%B0%EF%BC%88Ugly%20Number%EF%BC%89%E3%80%82%E6%B1%82%E6%8C%89%E4%BB%8E%E5%B0%8F%E5%88%B0%E5%A4%A7%E7%9A%84%E9%A1%BA%E5%BA%8F%E7%9A%84%E7%AC%AC%20n%20%E4%B8%AA%E4%B8%91%E6%95%B0%E3%80%82%0A%60%60%60%0A%E8%BE%93%E5%85%A5%3A%20n%20%3D%2010%0A%E8%BE%93%E5%87%BA%3A%2012%0A%E8%A7%A3%E9%87%8A%3A%201%2C%202%2C%203%2C%204%2C%205%2C%206%2C%208%2C%209%2C%2010%2C%2012%20%E6%98%AF%E5%89%8D%2010%20%E4%B8%AA%E4%B8%91%E6%95%B0%E3%80%82%0A%60%60%60%0A%0A%23%23%23%20c%20plus%0A%0A%0A%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%0A%0A%5B%E9%A2%98%E8%A7%A3%5D(https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fchou-shu-lcof%2Fsolution%2Fchou-shu-ii-qing-xi-de-tui-dao-si-lu-by-mrsate%2F)%0A%60%60%60c%0Aclass%20Solution%20%7B%0Apublic%3A%0A%20%20%20%20int%20nthUglyNumber(int%20n)%20%7B%0A%20%20%20%20%20%20%20%20vector%3Cint%3E%20dp(n%2C%200)%3B%0A%20%20%20%20%20%20%20%20dp%5B0%5D%20%3D%201%3B%0A%20%20%20%20%20%20%20%20int%20p2%20%3D%200%2C%20p3%20%3D%200%2C%20p5%20%3D%200%3B%2F%2F%E7%94%A8%E4%B8%89%E4%B8%AA%E5%BF%AB%E6%85%A2%E6%8C%87%E9%92%88%E7%BB%B4%E6%8A%A4%E4%B8%89%E4%B8%AA%E7%BB%84%E6%95%B0%E3%80%82%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%20n%3B%20i%2B%2B)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20dp%5Bi%5D%20%3D%20min(min(dp%5Bp2%5D%20%202%2C%20dp%5Bp3%5D%20%203)%2C%20dp%5Bp5%5D%20%205)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(dp%5Bi%5D%20%3D%3D%20dp%5Bp2%5D%20%202)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20p2%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(dp%5Bi%5D%20%3D%3D%20dp%5Bp3%5D%20%203)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20p3%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(dp%5Bi%5D%20%3D%3D%20dp%5Bp5%5D%20%205)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20p5%2B%2B%3B%20%20%20%0A%20%20%20%20%20%20%20%20%7D%20%0A%20%20%20%20%20%20%20%20return%20dp%5Bn%20-%201%5D%3B%0A%20%20%20%20%7D%0A%7D%3B%0A%0A%60%60%60%0A%0A*