題目：我們把只包含因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如6、8都是丑數(shù)，但14不是，因為它包含因子7。習慣上我們把1當做是第一個丑數(shù)。求按從小到大的順序的第1500個丑數(shù)。
分析：這是一道在網(wǎng)絡上廣為流傳的面試題，據(jù)說google曾經(jīng)采用過這道題。
算法一：所謂一個數(shù)m是另一個數(shù)n的因子，是指n能被m整除，也就是n % m == 0。根據(jù)丑數(shù)的定義，丑數(shù)只能被2、3和5整除。也就是說如果一個數(shù)如果它能被2整除，我們把它連續(xù)除以2；如果能被3整除，就連續(xù)除以3；如果能被5整除，就除以連續(xù)5。如果最后我們得到的是1，那么這個數(shù)就是丑數(shù)，否則不是。
#includeusing?namespace?std;
int?GetUglyNum1(int?n)
{
int?i,?temp,?time=0;
for(i=1;?;?i++)
{
temp=i;
while(temp%2==0)
temp/=2;
while(temp%3==0)
temp/=3;
while(temp%5==0)
temp/=5;
if(temp==1)
{
time++;
if(time==n)
break;
}
}
return?i;
}
void?main()
{
int?n;
cout<>n;
cout<<GetUglyNum1(n)<<endl;
}
該算法非常直觀，代碼也非常簡潔，但最大的問題我們每個整數(shù)都需要計算。即使一個數(shù)字不是丑數(shù)，我們還是需要對它做求余數(shù)和除法操作。因此該算法很耗時。
???????? 接下來我們換一種思路來分析這個問題，試圖只計算丑數(shù)，而不在非丑數(shù)的整數(shù)上花費時間。根據(jù)丑數(shù)的定義，丑數(shù)應該是另一個丑數(shù)乘以2、3或者5的結果（1除外）。因此我們可以創(chuàng)建一個數(shù)組，里面的數(shù)字是排好序的丑數(shù)。里面的每一個丑數(shù)是前面的丑數(shù)乘以2、3或者5得到的。
這種思路的關鍵在于怎樣確保數(shù)組里面的丑數(shù)是排好序的。我們假設數(shù)組中已經(jīng)有若干個丑數(shù)，排好序后存在數(shù)組中。我們把現(xiàn)有的最大丑數(shù)記做M。現(xiàn)在我們來生成下一個丑數(shù)，該丑數(shù)肯定是前面某一個丑數(shù)乘以2、3或者5的結果。我們首先考慮把已有的每個丑數(shù)乘以2。在乘以2的時候，能得到若干個結果小于或等于M的。由于我們是按照順序生成的，小于或者等于M肯定已經(jīng)在數(shù)組中了，我們不需再次考慮；我們還會得到若干個大于M的結果，但我們只需要第一個大于M的結果，因為我們希望丑數(shù)是按從小到大順序生成的，其他更大的結果我們以后再說。我們把得到的第一個乘以2后大于M的結果，記為M2。同樣我們把已有的每一個丑數(shù)乘以3和5，能得到第一個大于M的結果M3和M5。那么下一個丑數(shù)應該是M2、M3和M5三個數(shù)的最小者。
前面我們分析的時候，提到把已有的每個丑數(shù)分別都乘以2、3和5，事實上是不需要的，因為已有的丑數(shù)是按順序存在數(shù)組中的。對乘以2而言，肯定存在某一個丑數(shù)T2，排在它之前的每一個丑數(shù)乘以2得到的結果都會小于已有最大的丑數(shù)，在它之后的每一個丑數(shù)乘以2得到的結果都會太大。我們只需要記下這個丑數(shù)的位置，同時每次生成新的丑數(shù)的時候，去更新這個T2。對乘以3和5而言，存在著同樣的T3和T5。
#includeusing?namespace?std;
int?Min(int?num1,?int?num2,?int?num3)
{
int?min=(num1<num2)?num1:num2;
min=(min<num3)?min:num3;
return?min;
}
int?GetUglyNum2(int?n)
{
if(n<=0)
return?0;
int?*pUgly=new?int[n];
pUgly[0]=1;
int?nextUglyIndex=1;
int?*p2=pUgly;
int?*p3=pUgly;
int?*p5=pUgly;
while(nextUglyIndex?<?n)
{
int?min=Min(*p2*2,?*p3*3,?*p5*5);
pUgly[nextUglyIndex]=min;
while(*p2*2<=min)?p2++;
while(*p3*3<=min)?p3++;
while(*p5*5<=min)?p5++;
nextUglyIndex++;
}
int?ugly=pUgly[n-1];
delete[]?pUgly;
return?ugly;
}
void?main()
{
int?n;
cout<>n;
?????????cout<<GetUglyNum2(n)<<endl;
}第一種思路相比，這種算法不需要在非丑數(shù)的整數(shù)上做任何計算，因此時間復雜度要低很多。當然我們也要指出，第二種算法由于要保存已經(jīng)生成的丑數(shù)，因此需要一個數(shù)組，從而需要額外的內存。第一種算法是沒有這樣的內存開銷的。
?
下載文檔
