leetcode算法练习【264】丑数 IIgit椰子奶糖的博客-

所有题目源代码：Git地址

题目

编写一个程序，找出第 n 个丑数。  丑数就是只包含质因数 2, 3, 5 的正整数。  示例:  输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 说明:    1 是丑数。 n 不超过1690。 

方案：动态规划,下一个丑数一定是从｛2,3,5｝的倍数中来，设置指针专门计算三者倍数，再去重即可

class Solution {         public int nthUglyNumber(int n) {             ArrayList<Integer> uglyNum = new ArrayList<>( );             uglyNum.add(1);             int p2 = 0;             int p3 = 0;             int p5 = 0;             int num2 = uglyNum.get(p2) * 2;             int num3 = uglyNum.get(p2) * 3;             int num5 = uglyNum.get(p2) * 5;             int i = 0;             while (uglyNum.size( ) < n) {                  if (num2 <= num3 && num2 <= num5) {                     if (num2 > uglyNum.get(i)) {                         uglyNum.add(num2);                         i++;                     }                     p2++;                     num2 = uglyNum.get(p2) * 2;                 } else if (num3 < num2 && num3 <= num5) {                     if (num3 > uglyNum.get(i)) {                         uglyNum.add(num3);                         i++;                     }                     p3++;                     num3 = uglyNum.get(p3) * 3;                  } else {                     if (num5 > uglyNum.get(i)) {                         uglyNum.add(num5);                         i++;                     }                     p5++;                     num5 = uglyNum.get(p5) * 5;                 }             }             return uglyNum.get(n-1);         }     }  

复杂度计算

• 时间复杂度：O(n)
• 空间复杂度：O(n)

杂记

• 发现leetcode一个小bug，我在自己造类的时候，或者说自己弄了个构造函数，他似乎不执行，可能机制上没考虑到这个，其实也没太大必要。