丑数

丑数

DESC1:

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1:

输入: 6
输出: true
解释: 6 = 2 × 3

示例 2:

输入: 8
输出: true
解释: 8 = 2 × 2 × 2

示例 3:

输入: 14
输出: false
解释: 14 不是丑数，因为它包含了另外一个质因数 7。

说明：

    1 是丑数。
    输入不会超过 32 位有符号整数的范围: [−231,  231 − 1]。

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

CODE1:

JAVA:

class Solution {public boolean isUgly(int n) {if (n <= 0) {return false;}while (n%2==0) {n/=2;}while (n%3==0) {n/=3;}while (n%5==0) {n/=5;}//如果是丑数，满足n=2^x*3^y*5^z，最后n==1return n == 1;}
}

NOTES:

1. 丑数n满足, 所以通过不断除以2，3，5，最后n肯定为1，否则不是丑数；

DESC2:

编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

示例:

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

说明:  

    1 是丑数。
    n 不超过1690。

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

CODE2:

JAVA:

class Solution {public int nthUglyNumber(int n) {if (n <= 0) {return -1;} else if (n == 1) {return 1;}int[] arr = new int[n];arr[0] = 1;int index2=0, index3=0, index5=0;for (int i=1; i<n; i++) {int v2 = arr[index2]*2;int v3 = arr[index3]*3;int v5 = arr[index5]*5;arr[i] = Math.min(Math.min(v2, v3), v5);//不能if else ，最小值相等情况，对应index都加1，不然会重复，index含义是2，3，5对应最小值的位置if (arr[i] == v2) index2++;if (arr[i] == v3) index3++;if (arr[i] == v5) index5++;}return arr[n-1];}
}

NOTES:

1. 一个丑数n，基于公式可知，2*n,3*n,5*n这三个数也为丑数，如n=1时，2，3，5均是丑数，n=2时，4，6，10均是丑数；
2. 已知1是最小的丑数，可以通过对其分别不断乘2，乘3，乘5得到其他丑数，并在其中找到最小的一个作为第2个丑数，但重要的怎么将4(1*2*2)排在5(1*5)前面，通过维持三个指针来记录当前乘以2、乘以3、乘以5的最小值，然后当其被选为新的最小值后，要把相应的指针+1；