剑指offer--丑数（java）

叁歲伎倆 2021-11-02 16:10 251阅读 0赞

### 剑指offer--丑数 ###

两种常见解法：

1.  遍历判断丑数。从2开始判断当前数是否为丑数，如果是则计数+1，直到计数达到N为止。  
    这个方法是计算每一个数是否为丑数，时间开销大。不推荐  
    **时间复杂度：**
    
        public int GetUglyNumber_Solution(int index) { 
        	int cnt = 1;
        	int n = 2;
        	while(cnt<index) { 
        		if(isUgly(n)) { 
        			cnt++;
        		}
        		n++;
        	}
            return n-1;
        }
        
        private boolean isUgly(int n) { 
        	while(n%2==0 && n!=1) { 
        		n=n/2;
        	}
        	while(n%3==0 && n!=1) { 
        		n=n/3;
        	}
        	while(n%5==0 && n!=1) { 
        		n=n/5;
        	}
        	if(n==1) { 
        		return true;
        	}
        	return false;
        }

2.构造丑数，直到找到第N个丑数。  
丑数一定是前面某一个丑数乘2，乘3或者乘5得到的。所以我们可以找到大于目前已知丑数的最小值，就是下一个丑数，直到找到第N个丑数为止。但是这个需要保存找到的所有丑数，空间开销较大。  
**时间复杂度：**

public int GetUglyNumber_Solution(int index) { 
        	if(index == 0) { 
        		return 0;
        	}
        	int cnt = 1;
        	int[] uglyNumArr = new int[index];
        	int index2 = 0;
        	int index3 = 0;
        	int index5 = 0;
        	uglyNumArr[0] = 1;
        	while(cnt<index && index2<index && index3<index && index5<index) { 
        		uglyNumArr[cnt] = Mymin(uglyNumArr[index2] *2, uglyNumArr[index3]*3, uglyNumArr[index5]*5);
        		while(uglyNumArr[index2] *2 <= uglyNumArr[cnt]) { 
        			index2++;
        		}
        		while(uglyNumArr[index3] *3 <= uglyNumArr[cnt]) { 
        			index3++;
        		}
        		while(uglyNumArr[index5] *5 <= uglyNumArr[cnt]) { 
        			index5++;
        		}
        		cnt++;
        	}
            return uglyNumArr[cnt-1];
        }
    
    	private int Mymin(int i, int j, int k) { 
    		int minTemp = (i>j)?j:i;
    		return (minTemp>k)?k:minTemp;
    	}