算法題：尋找丑數(shù)
這是一道在訂閱的blog上看到的題目，覺得比較有意思建邓，就動(dòng)手做了一下磷瘤。
何為丑數(shù)?
丑數(shù)(Ugly number)是指其因子中只包含2、3贱田、5的整數(shù)，類如6嘴脾、20男摧、36都是丑數(shù)，而7统阿、19彩倚、28則不是丑數(shù)筹我。特別的：1是最小的丑數(shù)
題目：求從小大到的情況下第1500個(gè)丑數(shù)
解題過程：
- 原始解法:
從1開始扶平，判斷當(dāng)前數(shù)字是否丑數(shù)，不是則跳至下一個(gè)數(shù)字蔬蕊，是的話下標(biāo)+1结澄，如果下標(biāo)增加到指定的數(shù)字，則此時(shí)對(duì)應(yīng)的數(shù)字為要求的丑數(shù)岸夯。這個(gè)解法簡(jiǎn)單粗暴麻献，可以說毫無技術(shù)含量。因?yàn)槊恳粋€(gè)數(shù)都要與2猜扮、3勉吻、5輾轉(zhuǎn)相處，并且要遍歷答案之前的每一個(gè)自然數(shù)旅赢，時(shí)間復(fù)雜度太差齿桃。
- 改進(jìn)解法:
實(shí)際上我們可以試圖跳過那些不是丑數(shù)的自然數(shù)，考慮一下丑數(shù)是怎么得來的：從1開始煮盼，12＝2短纵，13=3，1*5=5僵控，然后從得到的2香到、3、5繼續(xù)乘以對(duì)應(yīng)的2、3悠就、5得到新的數(shù)字千绪。這樣得到的數(shù)字都是丑數(shù)，因?yàn)椴豢赡馨渌囊蜃庸ＦⅰＤ敲次覀兛梢試L試著來構(gòu)造一個(gè)從小到大排列的數(shù)組翘紊，數(shù)組的長(zhǎng)度就是我們需要的丑數(shù)序號(hào)。
接下來的問題是：如何保持?jǐn)?shù)組在構(gòu)造的過程中是有序的藐唠？
假設(shè)我們現(xiàn)在有了部分?jǐn)?shù)組帆疟，要添加一個(gè)新的丑數(shù)。新的丑數(shù)必然是從已有的數(shù)中宇立，分別乘2踪宠、3、5之后獲得妈嘹，為保持有序我們只取其中最小的數(shù)字柳琢，因?yàn)檫@三個(gè)數(shù)字中間也許還有其他的丑數(shù)。實(shí)際上這樣存在不必要的計(jì)算：可能存在一些數(shù)字润脸，乘以對(duì)應(yīng)的2柬脸、3、5之后也比當(dāng)前存在的最大丑數(shù)要小毙驯，而我們只需要乘以2倒堕、3、5之后比當(dāng)前最大丑數(shù)大的那個(gè)數(shù)爆价。所以垦巴，對(duì)應(yīng)2、3铭段、5這三個(gè)因子骤宣，我們應(yīng)該保存三個(gè)位置，使得這三個(gè)位置上的數(shù)字乘以對(duì)應(yīng)的2序愚、3憔披、5之后比當(dāng)前最大丑數(shù)大。怎么找爸吮？很簡(jiǎn)單芬膝，每次插入新的丑數(shù)之后，我們更新一下這三個(gè)數(shù)的位置就可以了拗胜。下一次就對(duì)這三個(gè)位置的數(shù)字分別乘以2蔗候、3、5埂软，找出最小的插入數(shù)組锈遥。這樣我們就保證了數(shù)組有序纫事，并盡量減少了不必要的計(jì)算。
C++代碼實(shí)現(xiàn):
#include <iostream>
int get_min_number(int a, int b, int c)
{
int min_ab = std::min(a,b);
return std::min(min_ab, c);
}
int find_ugly_number(int target)
{
if (target < 1)
return 0;
int* array = new int[target];
array[0] = 1;
int *pos2 = array;
int *pos3 = array;
int *pos5 = array;
int index = 1;
while (index < target)
{
int cur_max = get_min_number(*pos2*2, *pos3*3,*pos5*5);
array[index++] = cur_max;
while (*pos2*2 <= cur_max)
pos2++;
while (*pos3*3 <= cur_max)
pos3++;
while (*pos5*5 <= cur_max)
pos5++;
}
int ret = array[target-1];
delete [] array;
return ret;
}
int main()
{
int index = 1500;
int result = find_ugly_number(index);
std::cout << result << std::endl;
return 0;
}
代碼也被我放在我Github的issues庫(kù)中所灸，點(diǎn)擊查看
