济南网站建设代理,自己开个托管班需要什么手续,网站反链接,网站建设90g 吾爱破解文章目录 刷题前唠嗑题目#xff1a;无限集中的最小数字题目描述代码与解题思路偷看大佬题解 结语 刷题前唠嗑 LeetCode#xff1f;启动#xff01;#xff01;#xff01;
今天的题目也比较的简单#xff0c;因为数据量不大#xff0c;所以什么做法都能过的去
题目无限集中的最小数字题目描述代码与解题思路偷看大佬题解 结语 刷题前唠嗑 LeetCode启动
今天的题目也比较的简单因为数据量不大所以什么做法都能过的去
题目无限集中的最小数字
题目链接2336. 无限集中的最小数字
题目描述 代码与解题思路
type SmallestInfiniteSet struct {mp map[int]boolless int
}func Constructor() SmallestInfiniteSet {tmp : map[int]bool{}for i : 1; i 1001; i {tmp[i] true}return SmallestInfiniteSet{mp: tmp,less: 1,}
}func (this *SmallestInfiniteSet) PopSmallest() int {this.mp[this.less] falsetmp : this.lessfor i : 1; i 1001; i {if this.mp[i] true {this.less ibreak}}return tmp
}func (this *SmallestInfiniteSet) AddBack(num int) {this.mp[num] trueif num this.less {this.less num}
}好吧我承认我的代码确实是有点屎山具体来说就是开一个 1000 的 map然后暴力模拟出来这种做法和 C 直接用 set 自动排序然后往 set 里面插入 1000 条数据然后 pop 和 push 没啥区别。。非常的暴力
很难过刷了大半年算法了磕磕碰碰还是只会暴力解题哭了但是看到题目说数据量只有 1000这谁能忍得住呀呜呜
偷看大佬题解
class SmallestInfiniteSet {
public:vectorbool vis;priority_queueint, vectorint, greaterint q;int idx;SmallestInfiniteSet() : idx(1) {vis.resize(1010, false);}int popSmallest() {int ans -1;if (!q.empty()) {ans q.top();q.pop();vis[ans] false;} else {ans idx;}return ans;}void addBack(int x) {if (x idx || vis[x]) return;if (x idx - 1) {idx--;} else {q.push(x);vis[x] true;}}
};比较操蛋的事情大佬的题解如果用 go 来实现那代码量估计是不小go 可没有给堆要我手撕一个那我可又要写屎山了所以就用 C 代码冒充一下孩子的 C 功底还是在的大概也可能已经忘光了
主要的思路是这样的通过一个 bool 数组来记录这个数是否存在通过一小根堆的优先级对列维护一个小堆让我们能 log(N) 的获取存在的最小数。
结语
想念 STL 了C 确实是最好写算法的语言
