You have a set which contains all positive integers [1, 2, 3, 4, 5, ...]
.
Implement the SmallestInfiniteSet
class:
SmallestInfiniteSet()
Initializes the SmallestInfiniteSet object to contain all positive integers.int popSmallest()
Removes and returns the smallest integer contained in the infinite set.void addBack(int num)
Adds a positive integernum
back into the infinite set, if it is not already in the infinite set.
Example 1:
Input ["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"] [[], [2], [], [], [], [1], [], [], []] Output [null, null, 1, 2, 3, null, 1, 4, 5] Explanation SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet(); smallestInfiniteSet.addBack(2); // 2 is already in the set, so no change is made. smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set. smallestInfiniteSet.addBack(1); // 1 is added back to the set. smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and // is the smallest number, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.
Constraints:
1 <= num <= 1000
- At most
1000
calls will be made in total topopSmallest
andaddBack
.
无限集中的最小数字。
现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。
实现 SmallestInfiniteSet 类:
SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。
int popSmallest() 移除 并返回该无限集中的最小整数。
void addBack(int num) 如果正整数 num 不 存在于无限集中,则将一个 num 添加 到该无限集中。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/smallest-number-in-infinite-set
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路是最小堆 + hashset。初始化的时候,我们将 1 - 1000 这些数字都分别放入最小堆和 hashset 中。
pop() 很好判断,就是从最小堆中弹出一个元素即可,同时在 hashset 中也移除这个元素。
addBack() 需要判断最小堆中是否已经存在这个数字了,如果不存在才加回去。注意 testcase 中对于 add 操作,给的数字不一定是已经弹出的元素。
时间O(nlogn)
空间O(n)
Java实现
1 class SmallestInfiniteSet { 2 PriorityQueue<Integer> queue; 3 Set<Integer> set; 4 5 public SmallestInfiniteSet() { 6 queue = new PriorityQueue<>(); 7 set = new HashSet<>(); 8 for (int i = 1; i <= 1000; i++) { 9 queue.offer(i); 10 set.add(i); 11 } 12 } 13 14 public int popSmallest() { 15 if (!queue.isEmpty()) { 16 set.remove(queue.peek()); 17 return queue.poll(); 18 } 19 return -1; 20 } 21 22 public void addBack(int num) { 23 if (!set.contains(num)) { 24 set.add(num); 25 queue.offer(num); 26 } 27 } 28 } 29 30 /** 31 * Your SmallestInfiniteSet object will be instantiated and called as such: 32 * SmallestInfiniteSet obj = new SmallestInfiniteSet(); 33 * int param_1 = obj.popSmallest(); 34 * obj.addBack(num); 35 */
- LeetCode Infinite Smallest Number 2336leetcode infinite smallest number smallest recover number pat_a lexicographically string_medium leetcode smallest lexicographically palindrome leetcode smallest leetcode largest number string leetcode number happy 202 leetcode croaking minimum number rectangle leetcode number ships leetcode number clock valid leetcode答案 数学number