2022/08/02------Ugly number

题目描述

剑指 Offer 49. 丑数

解题思路

解题思路一：Make judgments while increasing numbers,Make the most of the ugly numbers you saved earlier.缺点：超出时间限制.

优化思路：It should not be judged numerically one by one,To take full advantage of the big ugly numbers are composed of the clown numbers,to get beforenThe specific value of the number.Avoid useless judgments,优化时间效率.

代码实现

思路一代码实现：

package cz;

import java.util.ArrayList;
import java.util.List;

public class NthUglyNumber_0802 {
    

	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
		int n=11;
		System.out.print(nthUglyNumber(n));

	}	
	public static int nthUglyNumber(int n) {
    
		
		List<Integer> mlist=new ArrayList<>();
		int count=1;
		int res=1;
		mlist.add(res);
		while(true) {
    
			
			if(count==n)break;
			else {
    
				res+=1;
				if(res%2==0&&mlist.contains(res/2)||res%3==0&&mlist.contains(res/3)||res%5==0&&mlist.contains(res/5)) {
    
					count++;
					mlist.add(res);
				}
			}
		}		
		return res;
    }

}

The optimization idea code is implemented as follows：

package cz;

import java.util.ArrayList;
import java.util.List;

public class NthUglyNumber_0802 {
    

	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
		int n=11;
		System.out.print(nthUglyNumber(n));

	}
	
	
	
	public static int nthUglyNumber(int n) {
    
		
		int[] ugly=new int [n];
		ugly[0]=1;
		int i=0,j=0,k=0;
		
		for(int index=1;index<n;index++)
		{
    
			int temp=Math.min(ugly[i]*2, Math.min(ugly[j]*3, ugly[k]*5));
			//避免重复
			if(temp==ugly[i]*2)i++;
			if(temp==ugly[j]*3)j++;
			if(temp==ugly[k]*5)k++;
			ugly[index]=temp;
		}
		
		
		return ugly[n-1];

    }

}