把只包括因子2、3和5的數稱作丑數（Ugly Number）。例如6、8都是丑數，但14不是，由于它包括因子7。 習慣上我們把1當作是第1個丑數。求按從小到大的順序的第N個丑數。
暴力的不說了
1個數只能是2、3、5因子組成是丑數
丑數M，1定是由于前面的數乘以2、3、5后選取的最小值
所有可以定義1個數組寄存丑數，當時第i個丑數的時候，將前面的i⑴個丑數分別乘以2、3、5選取最小值（并且不是前面i⑴個丑數）就是第i個丑數
下面程序超時了
import java.util.*;
public class Solution {
public int GetUglyNumber_Solution(int index) {
ArrayList<Integer> u = new ArrayList<Integer>();
u.add(0);
u.add(1);
if(index == 1)
return u.get(index);
int preIndex = 2;
while(preIndex <= index){
int preU = Integer.MAX_VALUE;
for(int i=1;i<u.size() ;i++){
int ui = u.get(i);
if(!u.contains(ui*2))
preU = Math.min(preU,ui*2);
if(!u.contains(ui*3))
preU = Math.min(preU,ui*3);
if(!u.contains(ui*5))
preU = Math.min(preU,ui*5);
}
u.add(preU);
preIndex ++;
}
return u.get(index);
}
}判斷是不是已存在、找到最小值時間復雜度都是比較高的
在找下1個丑數時候，盡心了許多重復計算
計算M丑數，只與N有關，而與小于N的無關
而這個N應當包括：N2、N3、N5這3個數，我們只要找到這3個數就行了，這需要3個指針了，3個指針指向不同的N，選取這個N后，其指針后移1位
這個和書上講的很類似，我只是換了1個角度理解，重點是上面的方法讓我很容易想到了這個方法
import java.util.*;
public class Solution {
public int GetUglyNumber_Solution(int index) {
ArrayList<Integer> u = new ArrayList<Integer>();
u.add(0);
u.add(1);
if(index == 1)
return u.get(index);
int i1 = 1;
int i2 = 1;
int i3 = 1;
int preIndex = 2;
while(preIndex <= index){
int preU = Integer.MAX_VALUE;
int u1 = u.get(i1) * 2;
int u2 = u.get(i2) * 3;
int u3 = u.get(i3) * 5;
preU = Math.min(preU,u1);
preU = Math.min(preU,u2);
preU = Math.min(preU,u3);
if(preU == u1){
i1++;
}
if(preU == u2){
i2++;
}
if(preU == u3){
i3++;
}
u.add(preU);
preIndex ++;
}
return u.get(index);
}
}
下一篇 仿百度地圖街景實現
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
