把只包含質因子 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 是第一個丑數，我們從 1 開始乘以 2、3、5 就得到 2、3、5 三個丑數，從這三個丑數出發再乘以 2、3、5 就得到 4、6、10、6、9、15、10、15、25 九個丑數，明顯發現這樣子得到的丑數不僅出現重復，而且還是無序的，
一個數分別乘以 2、3、5 可以得到三個不同的丑數，因此我們可以維護三個佇列，用于存放一個丑數分別乘以 2、3、5 對應得到的丑數，與此同時，我們還要有一個陣列，用于存放當前這個丑數
- 丑數陣列：1
- 乘以 2 的佇列：2
- 乘以 3 的佇列：3
- 乘以 5 的佇列：5
選擇三個佇列中最小的一個數 2 加入陣列，同時將該最小的數乘以 2、3、5 放入三個佇列 - 丑數陣列：1、2
- 乘以 2 的佇列：4
- 乘以 3 的佇列：3、6
- 乘以 5 的佇列：5、10
選擇三個佇列中最小的一個數 3 加入陣列，同時將該最小的數乘以 2、3、5 放入三個佇列 - 丑數陣列：1、2、3
- 乘以 2 的佇列：4、6
- 乘以 3 的佇列：6、9
- 乘以 5 的佇列：5、10、15
，，，，，，
于是我們就可以得到按從小到大的順序的第 N 個丑數
實際上我們也沒必要維護三個佇列，只需要三個指標即可，分別為 p2、p3、p5，表示乘以 2，乘以 3，乘以 5，指標對應陣列中的數乘以對應的質因子，就是對應佇列中最小的丑數
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index < 1) {
return 0;
}
int[] result = new int[index];
int p2 = 0, p3 = 0, p5 = 0;
result[0] = 1;
for(int i = 1; i < index; i++) {
result[i] = Math.min(result[p2]*2, Math.min(result[p3]*3, result[p5]*5));
if(result[i] == result[p2]*2) p2++;
if(result[i] == result[p3]*3) p3++;
if(result[i] == result[p5]*5) p5++;
}
return result[index - 1];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/176533.html
標籤：其他
下一篇：力扣初級演算法（四）【樹】