Re: [閒聊] 每日LeetCode已回收
2336. Smallest Number in Infinite Set
設計一個資料結構，這個資料結構有是一個集合且元素數量有無限個，實作：
- SmallestInfiniteSet()：初始化類別，集合一開始有無限個元素。
- int popSmallest()： 從集合移除最小元素並返回。
- void addBack(int num)：加入一個元素，如果元素已經在集合則忽略。
Example：
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.
思路：
1.用一個heap保存頂端最小元素，一個Set保存集合裡面是否包含重複值。
2.加入元素操作，下列情況之一不做處理：
* 要加入的元素大小高於於pop的數量，表示這個元素已存在沒被移除過。
* 元素不存在Set之中。
如果上面兩個都不滿足則把當前元素加入heap。
3.取出元素操作，如果set為空表示最頂端元素是count，返回count並加一
如果set不為空表示有元素被重新加入，從heap之中取頂端(最小)值。
Java Code：
-----------------------------------------------------
class SmallestInfiniteSet {
private final Set<Integer> set;
private final PriorityQueue<Integer> heap;
private int count;
public SmallestInfiniteSet() {
set = new HashSet<>();
heap = new PriorityQueue<>();
count = 1;
}
public int popSmallest() {
if (!set.isEmpty()) {
int res = heap.poll();
set.remove(res);
return res;
}
return count++;
}
public void addBack(int num) {
if (num < count && set.add(num)) {
heap.add(num);
}
}
}
-----------------------------------------------------
大guy是這樣 姆咪
--
https://i.imgur.com/3e5CZfj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1682415627.A.82B.html
推
04/25 17:45,
2年前
, 1F
04/25 17:45, 1F
推
04/25 17:45,
2年前
, 2F
04/25 17:45, 2F
推
04/25 17:47,
2年前
, 3F
04/25 17:47, 3F
討論串 (同標題文章)
完整討論串 (本文為第 300 之 719 篇)：