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, 12is the sequence of the first10ugly numbers.
Note that
1is typically treated as an ugly number.
Hint:
- The naive approach is to call
isUglyfor every number until you reach the n<sup style="box-sizing: border-box; position: relative; font-size: 12px; line-height: 0; vertical-align: baseline; top: -0.5em;">th one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
- An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
- The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L<sub style="box-sizing: border-box; position: relative; font-size: 12px; line-height: 0; vertical-align: baseline; bottom: -0.25em;">1, L<sub style="box-sizing: border-box; position: relative; font-size: 12px; line-height: 0; vertical-align: baseline; bottom: -0.25em;">2, and L<sub style="box-sizing: border-box; position: relative; font-size: 12px; line-height: 0; vertical-align: baseline; bottom: -0.25em;">3.
- Assume you have U<sub style="box-sizing: border-box; position: relative; font-size: 12px; line-height: 0; vertical-align: baseline; bottom: -0.25em;">k, the k<sup style="box-sizing: border-box; position: relative; font-size: 12px; line-height: 0; vertical-align: baseline; top: -0.5em;">th ugly number. Then U<sub style="box-sizing: border-box; position: relative; font-size: 12px; line-height: 0; vertical-align: baseline; bottom: -0.25em;">k+1 must be Min(L<sub style="box-sizing: border-box; position: relative; font-size: 12px; line-height: 0; vertical-align: baseline; bottom: -0.25em;">1 * 2, L<sub style="box-sizing: border-box; position: relative; font-size: 12px; line-height: 0; vertical-align: baseline; bottom: -0.25em;">2 * 3, L<sub style="box-sizing: border-box; position: relative; font-size: 12px; line-height: 0; vertical-align: baseline; bottom: -0.25em;">3 * 5).
題意就不翻譯了，意思就是把丑數(shù)從小到大排列，輸出制定位置的那個(gè)丑數(shù)是多少，按照上一題的那種樸素判斷當(dāng)然是行得通的，只要把1~n的數(shù)全部都驗(yàn)證一遍，自然可以找到第n個(gè)，但是認(rèn)真想想，一旦n大了之后，其實(shí)丑數(shù)的個(gè)數(shù)是不多的，也就是說驗(yàn)證成功的次數(shù)遠(yuǎn)遠(yuǎn)小于失敗的，所以用樸素的驗(yàn)證方式，顯然是相當(dāng)浪費(fèi)時(shí)間（事實(shí)上也是），所以我們的思路就是想到如何一個(gè)一個(gè)計(jì)算出丑數(shù)，找到其中的規(guī)律，主動(dòng)去計(jì)算丑數(shù)而不是被動(dòng)得驗(yàn)證是不是丑數(shù)
My Solution
(Java) Version 1 Time: 131ms:
計(jì)算丑數(shù)的原理當(dāng)然不難，不要想到這一點(diǎn)還是花了不少功夫，首先每個(gè)丑數(shù)都是由2,3,5相乘得來的，而且每一個(gè)相同乘數(shù)的個(gè)數(shù)還不定，比如有5個(gè)5，3個(gè)1之類的，所以只能從小到大一個(gè)一個(gè)算出來，然后我們又發(fā)現(xiàn)了每個(gè)丑數(shù)其實(shí)都是由前面小的丑數(shù)乘以2,3,5得來的，那就很明顯了，我們只要把前面的丑數(shù)都乘以2,3,5，然后結(jié)果里面最小的那個(gè)就一定是下一個(gè)丑數(shù)了
public class Solution {
public int nthUglyNumber(int n) {
int[] nums = new int[n];
nums[0]=1;
int max2=0,max3=0,max5=0,index;
for(int i=0;i<n-1;i++){
index=0;
while(max2<=nums[i]){
max2=nums[index]*2;
index++;
}
index=0;
while(max3<=nums[i]){
max3=nums[index]*3;
index++;
}
index=0;
while(max5<=nums[i]){
max5=nums[index]*5;
index++;
}
nums[i+1]=max2<max3?max2<max5?max2:max5<max3?max5:max3:max3<max5?max3:max5;
}
return nums[n-1];
}
}
(Java) Version 2 Time: 46ms (By luke.wang.7509):
這個(gè)解法的生成形式和上一個(gè)并無不同，不過上一個(gè)解法每一次都要從第一個(gè)丑數(shù)開始乘顯然是沒有必要的，因?yàn)橛泻芏嘀貜?fù)，這里就避免了這個(gè)問題
public class Solution {
public int nthUglyNumber(int n) {
if(n<=0) return 0;
int a=0,b=0,c=0;
List<Integer> table = new ArrayList<Integer>();
table.add(1);
while(table.size()<n)
{
int next_val = Math.min(table.get(a)*2,Math.min(table.get(b)*3,table.get(c)*5));
table.add(next_val);
if(table.get(a)*2==next_val) a++;
if(table.get(b)*3==next_val) b++;
if(table.get(c)*5==next_val) c++;
}
return table.get(table.size()-1);
}
}
(Java) Version 3 Time: 4ms (By TheKingRingReal):
DFS是深度優(yōu)先的搜索算法，這里我還沒能理解，不過從結(jié)果上看，已經(jīng)很顯然了……4ms快到媽都不認(rèn)得是誰
作者的解釋：
we can get a tree like this which contains all the ugly number ;just use three point to dfs because of I can not find the relationship between three point ; so we can think it just like this picture
each point 3 and 5 can have the 2_3and 2_5;3_5 child.and we can use a tricky in programming that if we meet 2_3=6 we should p2++;p3++;if 35:p5++;p3++;just like the code writ in DFS function*
public class Solution {
public int nthUglyNumber(int n) {
int[] dp=new int[n];dp[0]=1;
return DFS(dp,1,0,0,0,n);
}
private int DFS(int[] dp, int i, int p2, int p3, int p5, int n) {
if (i==n)return dp[n-1];
dp[i]=Math.min(dp[p2]*2, Math.min(dp[p3]*3,dp[p5]*5));
if (dp[i]==dp[p2]*2)p2++;
if(dp[i]==dp[p3]*3)p3++;
if (dp[i]==dp[p5]*5)p5++;
return DFS(dp, i+1, p2, p3, p5, n);
}
}
(Java) Version 4 Time: 2ms (By zmajia):
這個(gè)哈哈哈哈哈哈逗逼把測試樣例的極限試了出來，然后打表了哈哈哈哈哈哈，實(shí)在是太壞了，所以獲得了最快的速度，已知極限用打表的方式空間換時(shí)間還是很管用的
public class Solution {
static int[] save = new int[3000];
static int flag = 0;
public int nthUglyNumber(int n) {
if(flag == 0){
flag ++;
init();
}
return save[n-1];
}
public static void init(){
int _2 = 0, _3 = 0, _5 = 0;
save[0] = 1;
for(int i = 1; i < 3000; i++){
int min = Math.min(save[_2]*2, Math.min(save[_3]*3,save[_5]*5));
if(save[_2]*2 == min) {
save[i] = save[_2]*2;
_2 ++;
}
if(save[_3]*3 == min) {
save[i] = save[_3]*3;
_3 ++;
}
if(save[_5]*5 == min) {
save[i] = save[_5]*5;
_5 ++;
}
}
}
}
(Java) Version 5 Time: 108ms (By saharH):
TreeSet我沒有怎么研究過，雖然慢但這是我看到的最簡潔的做法，其中起作用的應(yīng)該就是TreeSet的一些特性了，值得研究
public class Solution {
public int nthUglyNumber(int n) {
TreeSet<Long> hs = new TreeSet<>(Arrays.asList(1l, 2l, 3l, 5l));
Long e = 1l;
while( n != 0){
e = hs.pollFirst();
hs.add(e * 2);
hs.add(e * 3);
hs.add(e * 5);
n--;
}
return e.intValue();
}
}
