JZ49 丑數
題目
我們先看到題目，把只包含質因子2、3和5的數稱作丑數（Ugly Number），例如6、8都是丑數，但14不是，因為它包含質因子7， 習慣上我們把1當做是第一個丑數，
方法1：質因數分解（暴力）
思路
演算法實作
- 一個很樸素的做法
- 從1~n每次+1，一直列舉，直到找到地N個丑數為止
- 那么還有一個待解決的問題，如何判斷當前數字是不是丑數呢？
- 我們總結一下丑數的性質：只能分解為2,3,5的如干次冪相乘的數，即設第個丑數為，則
res = 2*x + 3*y + 5*z - 那么我們只需要通過質因數分解，判斷他分解2,3,5后，是否為1，如果為1，則說明沒有其他的因數，否則則有其他因數，那么他就不是一個丑數
問題
當輸入數過大時，需要的時間會很長，所以此方法不行
代碼
package mid.JZ49丑數;
import java.util.ArrayList;
public class Solution {
public int GetUglyNumber_Solution(int index) {
int current = 1;
ArrayList<Integer> res = new ArrayList<>();
res.add(1);
while(true) {
if (res.size() == index) {
return res.get(res.size() - 1);
}
current++;
if (check(current)) {
res.add(current);
}
}
}
public boolean check(int num) {
while(num % 2 == 0) num /= 2;
while(num % 3 == 0) num /= 3;
while(num % 5 == 0) num /= 5;
return num == 1;
}
public static void main(String[] args) {
System.out.println(new Solution().GetUglyNumber_Solution(1500));
}
}
方法2
思路
- 有了上面的定義我們就可以知道，丑數的形式就是2x3y5z，所以我們可以定義一個陣列res，存盤第n個丑數，
- 因為我們要將丑數按從小到大的順序排序，所以我們就得將對應的丑數放在對應的下標位置，小的放前面，
- 這個時候上面我們的出來的丑數的格式就起作用了，丑數的形式無非就是這樣2x3y5z，所以我們就將res[n]去乘以 2、3、5，然后比較出最小的那個，就是我們當前的下一個丑數了，
代碼
package mid.JZ49丑數;
public class Solution {
public int GetUglyNumber_Solution(int index) {
if (index <= 6) return index;
int x = 0, y = 0, z = 0;
int[] res = new int[index];
res[0] = 1;
for (int i = 1; i < index; i++) {
res[i] = Math.min(res[x]*2, Math.min(res[y]*3, res[z]*5));
if (res[i] == res[x]*2) x++;
if (res[i] == res[y]*3) y++;
if (res[i] == res[z]*5) z++;
}
return res[index - 1];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/540446.html
標籤：其他
上一篇：巧如范金,精比琢玉,一分鐘高效打造精美詳實的Go語言技術簡歷(Golang1.18)
下一篇：redis—安裝以及可視化