条件:1.求包含因子2的所有数的集合,求包含因子3的所有数的集合,求包含因子5的所有数的集合。
2. 这三个集合中的数有交集,所以要去重。
3. 求的是从小到大的集合,需要返回最大值。
三路归并
三指针的思想,所以定义3个指针i, j, k。
vector存储的是丑数数组,一开始只有1个1,后面 动态添加元素进vector。
t取出的是3个指针分别指向的3个子数组(2 3 5)中的最小值。如果最小值是3个子数组中的哪一个,就把里面的指针i j k 增1。因为可能同时出现在多个数组,所以用3个if来表示。
最后输出vector的最后一位,就是第n个丑数。
时间复杂度
O(n)
class Solution {
public:
int getUglyNumber(int n) {
vector<int> res(1, 1);
// 定义三个指针
int i = 0, j = 0, k = 0;
while(res.size() < n) {
int t = min(res[i] * 2, min(res[j] * 3, res[k] * 5));
// 找到对应指针加一
if (t == (res[i] * 2)) i++;
if (t == (res[j] * 3)) j++;
if (t == (res[k] * 5)) k ++;
// 把t加入vector中
res.push_back(t);
}
return res.back(); // 返回最后一个元素
}
};