思路
这道题初见时只能用暴力解法,提交时不出意外的超时了。在leetcode上看了很多题解,
但是感觉都没有剑指offer书上说的清楚。
目前这道题的题解我只能写出详细的注释,关于思路的阐释还不能完全凝练。等到二刷的时候再填坑。
C++ 代码
class Solution {
public:
int min_in_three(int a, int b, int c){//找到三个数中的最小值
int res = (a < b) ? a : b;
res = (res < c) ? res : c;
return res;
}
int nthUglyNumber(int n) {
if(n <= 0)return 0;
int temp[1700];//leetcode上将n限定为小于1690的数
//temp是一个只包含丑数的序列,且丑数满足从小到大排列
temp[0] = 1;//第一位丑数等于1
//temp[next - 1]表示当前的丑数序列的最后一位,
//temp[next]是我们想要确定的下一个丑数
int next = 1, idx2 = 0, idx3 = 0, idx5 = 0;
//idx2、idx3、idx5是丑数序列中的索引
//它们分别代表着“恰到好处”的已经在序列中的丑数,具体来说
//temp[idx2]是第一个乘2大于temp[next - 1]的丑数
//temp[idx2 - 1]乘2小于等于temp[next - 1]
//同理,temp[idx3]是第一个乘3大于temp[next - 1]的丑数
//temp[idx3 - 1]乘3小于等于temp[next - 1]
//对于idx5也有同样的规则
while(next < n){//每次循环确定当前序列的下一个丑数
int min_ = min_in_three(temp[idx2] * 2, temp[idx3] * 3,
temp[idx5] * 5);//下一个丑数取三个可能丑数中的最小值
//这样做是为了不漏掉任何一个丑数
temp[next] = min_;//更新当前的丑数序列
//更新idx2、idx3和idx5
//这样做的目的是使idx2、idx3和idx5始终满足上述性质
//如果亲自手算一下会发现,如果这段代码中的while更换为if
//同样可以ac,因为每次大循环中都会进行判断,但while
//更符合算法的思想
while(temp[idx2] * 2 <= temp[next]) idx2 ++ ;
while(temp[idx3] * 3 <= temp[next]) idx3 ++ ;
while(temp[idx5] * 5 <= temp[next]) idx5 ++ ;
next ++ ;//使next指向下一个位置
}
return temp[next - 1];
}
};