題目描述
把只包含質因子2、3和5的數稱作丑數（Ugly Number），例如6、8都是丑數，但14不是，因為它包含質因子7， 習慣上我們把1當做是第一個丑數，求按從小到大的順序的第N個丑數，
思路
通俗易懂的解釋：
首先從丑數的定義我們知道，一個丑數的因子只有2,3,5，那么丑數p = 2 ^ x * 3 ^ y * 5 ^ z，換句話說一個丑數一定由另一個丑數乘以2或者乘以3或者乘以5得到，那么我們從1開始乘以2,3,5，就得到2,3,5三個丑數，在從這三個丑數出發乘以2,3,5就得到4，6,10,6，9,15,10,15,25九個丑數，我們發現這種方法會得到重復的丑數，而且我們題目要求第N個丑數，這樣的方法得到的丑數也是無序的，那么我們可以維護三個佇列：
（1）丑數陣列： 1
乘以2的佇列：2
乘以3的佇列：3
乘以5的佇列：5
選擇三個佇列頭最小的數2加入丑數陣列，同時將該最小的數乘以2,3,5放入三個佇列；
（2）丑數陣列：1,2
乘以2的佇列：4
乘以3的佇列：3，6
乘以5的佇列：5，10
選擇三個佇列頭最小的數3加入丑數陣列，同時將該最小的數乘以2,3,5放入三個佇列；
（3）丑數陣列：1,2,3
乘以2的佇列：4,6
乘以3的佇列：6,9
乘以5的佇列：5,10,15
選擇三個佇列頭里最小的數4加入丑數陣列，同時將該最小的數乘以2,3,5放入三個佇列；
（4）丑數陣列：1,2,3,4
乘以2的佇列：6，8
乘以3的佇列：6,9,12
乘以5的佇列：5,10,15,20
選擇三個佇列頭里最小的數5加入丑數陣列，同時將該最小的數乘以2,3,5放入三個佇列；
（5）丑數陣列：1,2,3,4,5
乘以2的佇列：6,8,10，
乘以3的佇列：6,9,12,15
乘以5的佇列：10,15,20,25
選擇三個佇列頭里最小的數6加入丑數陣列，但我們發現，有兩個佇列頭都為6，所以我們彈出兩個佇列頭，同時將12,18,30放入三個佇列；
……………………
疑問：
1.為什么分三個佇列？
丑數陣列里的數一定是有序的，因為我們是從丑數陣列里的數乘以2,3,5選出的最小數，一定比以前未乘以2,3,5大，同時對于三個佇列內部，按先后順序乘以2,3,5分別放入，所以同一個佇列內部也是有序的；
2.為什么比較三個佇列頭部最小的數放入丑數陣列？
因為三個佇列是有序的，所以取出三個頭中最小的，等同于找到了三個佇列所有數中最小的，
實作思路：
我們沒有必要維護三個佇列，只需要記錄三個指標顯示到達哪一步；“|”表示指標,arr表示丑數陣列；
（1）1
|2
|3
|5
目前指標指向0,0,0，佇列頭arr[0] * 2 = 2, arr[0] * 3 = 3, arr[0] * 5 = 5
（2）1 2
2 |4
|3 6
|5 10
目前指標指向1,0,0，佇列頭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，佇列頭arr[1] * 2 = 4, arr[1] * 3 = 6, arr[0] * 5 = 5
………………
牛客網鏈接
js代碼
function GetUglyNumber_Solution(index)
{
// write code here
if (index < 7) return index
let p2 = 0
let p3 = 0
let p5 = 0
let ugly
let arr = [1]
while (arr.length < index) {
ugly = Math.min(arr[p2]*2, arr[p3]*3, arr[p5]*5)
if (ugly === arr[p2]*2) p2++
if (ugly === arr[p3]*3) p3++
if (ugly === arr[p5]*5) p5++
arr.push(ugly)
}
return arr[arr.length-1]
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137709.html
標籤：其他
上一篇：206.反轉鏈表
下一篇：程式員小灰-演算法集錦