1-10题

11-20题

21-30题

31-40题

49.丑数

Medium
LeetCode

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

思路：
1.暴力解法：遍历所有自然数，每遍历到一个数就判断这个数是不是丑数，求出第n个丑数
2.利用丑数的性质，丑数只包含质因子 2、3 和 5，由此得知想要求得一个丑数可以通过一个丑数×2或者×3或者×5的方法求出来，那么这题就变成通过之前的丑数求之后的丑数的题了
设置三个指针，分别求指针指向的数(丑数)的2倍 3倍 5倍，三者比较得出最小的就是下一个丑数

public int nthUglyNumber(int n) {
        if(n < 0) return 0;
        int[] uglyArr = new int[n];
        uglyArr[0] = 1;
        int p2 = 0,p3 = 0,p5 = 0;
        for(int i=1;i<n;i++){
            int lastMaxUgly = uglyArr[i-1];
            while(lastMaxUgly >= uglyArr[p2]*2) p2++;
            while(lastMaxUgly >= uglyArr[p3]*3) p3++;
            while(lastMaxUgly >= uglyArr[p5]*5) p5++;
            uglyArr[i] = Math.min(Math.min(uglyArr[p2]*2,uglyArr[p3]*3),uglyArr[p5]*5);
        }
        return uglyArr[n-1];
    }

41-50题