首页 > 代码库 > Leetcode264. Ugly Number II JAVA语言
Leetcode264. Ugly Number II JAVA语言
Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. Note that 1 is typically treated as an ugly number, and n does not exceed 1690.
题意:找第N个丑数。N<1690.
public class Solution { public int nthUglyNumber(int n) { int[] result=new int[n]; result[0]=1; int begin=1; int m2=0,m3=0,m5=0; while(begin<n){ result[begin]=min(result[m2]*2,result[m3]*3,result[m5]*5); // System.out.println(result[begin]); while(result[m2]*2<=result[begin]){ m2++; } while(result[m3]*3<=result[begin]){ m3++; } while(result[m5]*5<=result[begin]){ m5++; } begin++; } return result[--begin]; } public static int min(int m2,int m3,int m5){ int temp=m2<m3?m2:m3; return m5<temp?m5:temp; } }
PS:要是利用前面的一个一个丑数挨个算到第N个,效率会很低。此时我们利用后面的丑数都是由前面的丑数*2,*3,*5得到,保存前面得到的丑数,就没有必要计算所有的了。效率提升。思路见剑指offer P183。
Leetcode264. Ugly Number II JAVA语言
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。