劍指Offer36--面試題49.醜數

• • • 題目描述
    • 代碼： 時間複雜度過高，未通過
    • 代碼：動态規劃

題目描述

我們把隻包含因子 2、3 和 5 的數稱作醜數（Ugly Number）。求按從小到大的順序的第 n 個醜數。

代碼： 時間複雜度過高，未通過

class Solution {
	 public int nthUglyNumber(int n) {
	        if(n == 1) return 1;
		        int count = 1;
		        int res = 1;
		        
		        for(int i=2;;i++){
		            if(findZhi(i)){
		                res = i;
		                count++; 
		            }
		            if(count == n) break;
		        }
		        return res;
	    }
    
	    //找出目前數的所有質數
	  public boolean findZhi(int num){
	    	boolean flag = true;
	        ArrayList<Integer> a = new ArrayList<Integer>();
	        for(int i=2; i<=num ;i++){
	            if(isZhi(i)){
	            	if(num%i==0&&i!=2&&i!=3&&i!=5) flag = false;  
	            }
	        }
	        return flag;
	        
	    }
	    
	    // 判斷是否為質數
	    public boolean isZhi(int num){
	        boolean flag = true;
	        for(int i=2; i<=Math.sqrt(num);i++){
	            if(num%i==0){
	                flag = false;
	                break;
	            }
	        }
	        return flag;
	    }
}
           

代碼：動态規劃

參考連結

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index==0)return 0;
        int a = 0, b = 0, c = 0;
        int[] dp = new int[index];
        dp[0] = 1;
        for(int i = 1; i < index; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[index - 1];

    }
}