題目：把只包含質因子2竭沫、3和5的數稱作丑數（Ugly Number）。例如6、8都是丑數鸟蟹，但14不是乌妙，因為它包含質因子7。 習慣上我們把1當做是第一個丑數建钥。求按從小到大的順序的第N個丑數藤韵。
練習地址
https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b
https://leetcode-cn.com/problems/chou-shu-lcof/
逐個判斷每個整數是不是丑數的解法，直觀但不夠高效
public class Solution {
public int GetUglyNumber_Solution(int index) {
if (index <= 0) {
return 0;
}
int number = 0;
for (int i = 0; i < index;) {
number++;
if (isUgly(number)) {
i++;
}
}
return number;
}
private boolean isUgly(int number) {
while (number % 2 == 0) {
number /= 2;
}
while (number % 3 == 0) {
number /= 3;
}
while (number % 5 == 0) {
number /= 5;
}
return number == 1;
}
}
復雜度分析
- 時間復雜度：O(nm)熊经。
- 空間復雜度：O(1)泽艘。
創(chuàng)建數組保存已經找到的丑數，用空間換時間的解法
public class Solution {
public int GetUglyNumber_Solution(int index) {
if (index <= 0) {
return 0;
}
int[] ugly = new int[index];
ugly[0] = 1;
for (int i = 1, multiply2 = 0, multiply3 = 0, multiply5 = 0; i < index; i++) {
ugly[i] = Math.min(ugly[multiply2] * 2, Math.min(ugly[multiply3] * 3, ugly[multiply5] * 5));
while (ugly[multiply2] * 2 <= ugly[i]) {
multiply2++;
}
while (ugly[multiply3] * 3 <= ugly[i]) {
multiply3++;
}
while (ugly[multiply5] * 5 <= ugly[i]) {
multiply5++;
}
}
return ugly[index - 1];
}
}
復雜度分析
- 時間復雜度：O(n)镐依。
- 空間復雜度：O(n)匹涮。
