問題：把只包含質(zhì)因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如6、8都是丑數(shù)，但14不是，因?yàn)樗|(zhì)因子7。 習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)。求按從小到大的順序的第N個(gè)丑數(shù)。

---

通俗易懂的解釋：

首先從丑數(shù)的定義我們知道，一個(gè)丑數(shù)的因子只有2,3,5，那么丑數(shù)p = 2 ^ x * 3 ^ y * 5 ^ z，換句話說一個(gè)丑數(shù)一定由另一個(gè)丑數(shù)乘以2或者乘以3或者乘以5得到，那么我們從1開始乘以2,3,5，就得到2,3,5三個(gè)丑數(shù)，在從這三個(gè)丑數(shù)出發(fā)乘以2,3,5就得到4，6,10,6，9,15,10,15,25九個(gè)丑數(shù)，我們發(fā)現(xiàn)這種方法會得到重復(fù)的丑數(shù)，而且我們題目要求第N個(gè)丑數(shù)，這樣的方法得到的丑數(shù)也是無序的。那么我們可以維護(hù)三個(gè)隊(duì)列：

（1）丑數(shù)數(shù)組： 1

乘以2的隊(duì)列：2

乘以3的隊(duì)列：3

乘以5的隊(duì)列：5

選擇三個(gè)隊(duì)列頭最小的數(shù)2加入丑數(shù)數(shù)組，同時(shí)將該最小的數(shù)乘以2,3,5放入三個(gè)隊(duì)列；

（2）丑數(shù)數(shù)組：1,2

乘以2的隊(duì)列：4

乘以3的隊(duì)列：3，6

乘以5的隊(duì)列：5，10

選擇三個(gè)隊(duì)列頭最小的數(shù)3加入丑數(shù)數(shù)組，同時(shí)將該最小的數(shù)乘以2,3,5放入三個(gè)隊(duì)列；

（3）丑數(shù)數(shù)組：1,2,3

乘以2的隊(duì)列：4,6

乘以3的隊(duì)列：6,9

乘以5的隊(duì)列：5,10,15

選擇三個(gè)隊(duì)列頭里最小的數(shù)4加入丑數(shù)數(shù)組，同時(shí)將該最小的數(shù)乘以2,3,5放入三個(gè)隊(duì)列；

（4）丑數(shù)數(shù)組：1,2,3,4

乘以2的隊(duì)列：6，8

乘以3的隊(duì)列：6,9,12

乘以5的隊(duì)列：5,10,15,20

選擇三個(gè)隊(duì)列頭里最小的數(shù)5加入丑數(shù)數(shù)組，同時(shí)將該最小的數(shù)乘以2,3,5放入三個(gè)隊(duì)列；

（5）丑數(shù)數(shù)組：1,2,3,4,5

乘以2的隊(duì)列：6,8,10，

乘以3的隊(duì)列：6,9,12,15

乘以5的隊(duì)列：10,15,20,25

選擇三個(gè)隊(duì)列頭里最小的數(shù)6加入丑數(shù)數(shù)組，但我們發(fā)現(xiàn)，有兩個(gè)隊(duì)列頭都為6，所以我們彈出兩個(gè)隊(duì)列頭，同時(shí)將12,18,30放入三個(gè)隊(duì)列；

……………………

疑問：

1.為什么分三個(gè)隊(duì)列？

丑數(shù)數(shù)組里的數(shù)一定是有序的，因?yàn)槲覀兪菑某髷?shù)數(shù)組里的數(shù)乘以2,3,5選出的最小數(shù)，一定比以前未乘以2,3,5大，同時(shí)對于三個(gè)隊(duì)列內(nèi)部，按先后順序乘以2,3,5分別放入，所以同一個(gè)隊(duì)列內(nèi)部也是有序的；

2.為什么比較三個(gè)隊(duì)列頭部最小的數(shù)放入丑數(shù)數(shù)組？

因?yàn)槿齻€(gè)隊(duì)列是有序的，所以取出三個(gè)頭中最小的，等同于找到了三個(gè)隊(duì)列所有數(shù)中最小的。

實(shí)現(xiàn)思路：

我們沒有必要維護(hù)三個(gè)隊(duì)列，只需要記錄三個(gè)指針顯示到達(dá)哪一步；“|”表示指針,arr表示丑數(shù)數(shù)組；

（1）1

|2

|3

|5

目前指針指向0,0,0，隊(duì)列頭arr[0] * 2 = 2,? arr[0] * 3 = 3,? arr[0] * 5 = 5

（2）1 2

2 |4

|3 6

|5 10

目前指針指向1,0,0，隊(duì)列頭arr[1] * 2 = 4,? arr[0] * 3 = 3, arr[0] * 5 = 5

（3）1 2 3

2| 4 6

3 |6 9

|5 10 15

目前指針指向1,1,0，隊(duì)列頭arr[1] * 2 = 4,? arr[1] * 3 = 6, arr[0] * 5 = 5

………………

---

代碼：

class Solution { public:int GetUglyNumber_Solution(int index) {// 0-6的丑數(shù)分別為0-6if(index < 7) return index;//p2，p3，p5分別為三個(gè)隊(duì)列的指針，newNum為從隊(duì)列頭選出來的最小數(shù)int p2 = 0, p3 = 0, p5 = 0, newNum = 1;vector<int> arr;arr.push_back(newNum);while(arr.size() < index) {//選出三個(gè)隊(duì)列頭最小的數(shù)newNum = min(arr[p2] * 2, min(arr[p3] * 3, arr[p5] * 5));//這三個(gè)if有可能進(jìn)入一個(gè)或者多個(gè)，進(jìn)入多個(gè)是三個(gè)隊(duì)列頭最小的數(shù)有多個(gè)的情況if(arr[p2] * 2 == newNum) p2++;if(arr[p3] * 3 == newNum) p3++;if(arr[p5] * 5 == newNum) p5++;arr.push_back(newNum);}return newNum;} };

?

總結(jié)

以上是生活随笔為你收集整理的剑指offer：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。