##題目描述 把只包含質因子2、3和5的數稱作丑數（Ugly Number），例如6、8都是丑數，但14不是，因為它包含質因子7， 習慣上我們把1當做是第一個丑數，求按從小到大的順序的第N個丑數，
思路
三個計算通道存放最近算出的三個丑數（可重復），最小的也在其中，f(n+1) = min(2pass1, 3pass2, 5*pass3)，
時間復雜度O(n)，空間復雜度O(n)，
代碼
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index < 1) return 0;
int[] num = new int[index];
num[0] = 1;
int a = 0, b = 0, c = 0;
for(int i = 1; i < index; i++) {
num[i] = Math.min(2*num[a], Math.min(3*num[b], 5*num[c]));
if(num[i] == 2*num[a]) a++;
if(num[i] == 3*num[b]) b++;
if(num[i] == 5*num[c]) c++;
}
return num[index-1];
}
}
筆記
三個if判斷必須獨立，不能寫成if-elseif-else形式，否則會出錯，因為三個通道可能會出現相等的情況，相等時通道也要更新，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83469.html
標籤：其他
上一篇：把陣列排成最小的數
下一篇：第一個只出現一次的字符