合并三数组就使用三个指针,同步比较元素,将最小的那个元素加入丑数数组,同时该元素所处的列表指针后移一位,再重复此过程,最后将得到丑数的结果列表。
class Solution {
public:
int getUglyNumber(int n) {
if(!n) return 0;
vector<int>ugly(n,0);//初始化丑数列表,赋初值0
ugly[0] = 1;//第一个丑数下标为0,就是1本身
int i = 0, j = 0 , k = 0;
for(int idx = 1; idx < n; idx++){
int tmp = min(ugly[i] * 2,min(ugly[j] * 3,ugly[k] * 5)); //C++不支持多个参数求最小值
//三个数组中哪一个最小,就将该丑数加入列表,同时指针后移
if(tmp == ugly[i] * 2) i++;
if(tmp == ugly[j] * 3) j++;
if(tmp == ugly[k] * 5) k++;
ugly[idx] = tmp;
}
return ugly[n-1];//返回第n个丑数,即下标为 n - 1
}
};