lc264.丑数
给你一个整数n，请你找出并返回第n个 丑数 。
丑数 就是只包含质因数 2、3和/或 5 的正整数。
输入：n = 10 输出：12 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
priority_queue ：
- 优先级最大的元素最先出队列
- empty()、size()、top()、front()、push_back()、pop_back()
- std::less<T> 和 std::greater<T> 都是以函数对象的方式定义在 <function> 头文件中
-
int values[]{ 4,1,2,3 }; std::priority_queue<int, std::deque<int>, std::greater<int> >copy_values(values, values+4);//{1,3,2,4}
unordered_set：
find(key):查找值为key的元素
count(key):在容器中查找值为key的元素的个数
size()：返回当前容器中存有元素的个数。
- 不再以键值对的形式存储数据，而是直接存储数据的值；
- 容器内部存储的各个元素的值都互不相等，且不能被修改。
- 不会对内部存储的数据进行排序
- 初始时堆为空。首先将最小的丑数 1 加入堆。
- 每次取出堆顶元素 x，则 x 是堆中最小的丑数，由于 2x,3x,5x也是丑数，因此将 2x,3x,5x 加入堆。
- 上述做***导致堆中出现重复元素的情况。为了避免重复元素，可以使用哈希集合去重，避免相同元素多次加入堆。
- 在排除重复元素的情况下，第 n 次从最小堆中取出的元素即为第 n个丑数。
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> factors = {2, 3, 5};
unordered_set<long> seen;
priority_queue<long, vector<long>, greater<long>> heap;
seen.insert(1L);
heap.push(1L);//将最小的丑数加入堆
int ugly = 0;
for (int i = 0; i < n; i++) {
long curr = heap.top();//每次取出堆顶元素x，x是堆中最小的丑数
heap.pop();//弹出堆顶
ugly = (int)curr;
for (int factor : factors) {
long next = curr * factor; //next=2;
if (!seen.count(next)) {//如果next不在seen里
seen.insert(next);
heap.push(next);//把2加入堆
}
}
}
return ugly;
}
};
投递华为等公司10个岗位 >
微软公司福利 59人发布