网站建设项目资金申请报告,htm网站,网站开发数据共享,福建工商网上登记平台其他系列文章导航 Java基础合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
三、代码
四、总结 前言
这是力扣的2336题#xff0c;难度为中等#xff0c;解题方案有很多种#xff0c;本文讲解我认为… 其他系列文章导航 Java基础合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
三、代码
四、总结 前言
这是力扣的2336题难度为中等解题方案有很多种本文讲解我认为最奇妙的一种。 一、题目描述
现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。
实现 SmallestInfiniteSet 类
SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。int popSmallest() 移除 并返回该无限集中的最小整数。void addBack(int num) 如果正整数 num 不 存在于无限集中则将一个 num 添加 到该无限集中。
示例 输入
[SmallestInfiniteSet, addBack, popSmallest, popSmallest, popSmallest, addBack, popSmallest, popSmallest, popSmallest]
[[], [2], [], [], [], [1], [], [], []]
输出
[null, null, 1, 2, 3, null, 1, 4, 5]解释
SmallestInfiniteSet smallestInfiniteSet new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2); // 2 已经在集合中所以不做任何变更。
smallestInfiniteSet.popSmallest(); // 返回 1 因为 1 是最小的整数并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 2 并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 3 并将其从集合中移除。
smallestInfiniteSet.addBack(1); // 将 1 添加到该集合中。
smallestInfiniteSet.popSmallest(); // 返回 1 因为 1 在上一步中被添加到集合中// 且 1 是最小的整数并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 4 并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 5 并将其从集合中移除。 提示
1 num 1000最多调用 popSmallest 和 addBack 方法 共计 1000 次 二、题解
这题的关键点是始终要保证无限集合是连续的。无限集合的范围可以认为是从 1 到正无穷大并且都是正整数。 这道我是用TreeSet和一个min变量来维护这个无限集合。为什么用TreeSet因为TreeSet支持维护元素的自然顺序。
TreeSet小于min的有序集合。
min有序集合的最小值。
添加元素的时候分为两种情况 添加元素的时候如果添加的值大于等于无限集合中的最小值 min 就不要添加因为无限集合是连续的添加的元素在无限集合中已经存在。简单点说比min还大的数不用加说明已经存在了 添加的元素如果小于无限集合的最小值 min 也不能直接添加如果贸然添加会导致无限集合不连续只需要把它添加到有序集合 TreeSet 中即可 TreeSet 中存放的值都是小于 min 的。所以要加在TreeSet中要靠TreeSet来维护。
删除元素的时候 删除的时候先判断有序集合 TreeSet 是否为空如果不为空说明存在比 min 还小的元素直接从 TreeSet 中删除。否则就从有序集合中删除 min 删除之后 min 值要加 1 。 三、代码
class SmallestInfiniteSet {TreeSetInteger set new TreeSet();int min 1;public SmallestInfiniteSet() {}public int popSmallest() {if (set.isEmpty()) {return min;//先返回再}return set.pollFirst();//弹出set的第一个元素并删除}public void addBack(int num) {if (num min) {//大于的话说明存在了set.add(num);}}
} 四、总结
使用TreeSet和min变量来维护一个无限集合保证集合的连续性。添加元素时若元素大于等于min则不添加若元素小于min则将其添加到TreeSet中。删除元素时先判断TreeSet是否为空若不为空则从TreeSet中删除元素若为空则将min值加1。该算法能够高效地添加和删除元素并保持集合的连续性。
该算法还可以用优先队列小根堆 hash表解题比较优秀。
