上次编辑到这里，代码来自缓存 点击恢复默认模板
class Skiplist {
public:
Skiplist() {
}
bool search(int target) {
}
void add(int num) {
}
bool erase(int num) {
}
};
/**
* Your Skiplist object will be instantiated and called as such:
* Skiplist* obj = new Skiplist();
* bool param_1 = obj->search(target);
* obj->add(num);
* bool param_3 = obj->erase(num);
*/
java 解法, 执行用时: 16 ms, 内存消耗: 48.4 MB, 提交时间: 2023-04-19 10:16:14
class Skiplist {
static final int MAX_LEVEL = 32;
static final double P_FACTOR = 0.25;
private SkiplistNode head;
private int level;
private Random random;
public Skiplist() {
this.head = new SkiplistNode(-1, MAX_LEVEL);
this.level = 0;
this.random = new Random();
}
public boolean search(int target) {
SkiplistNode curr = this.head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 target 的元素*/
while (curr.forward[i] != null && curr.forward[i].val < target) {
curr = curr.forward[i];
}
}
curr = curr.forward[0];
/* 检测当前元素的值是否等于 target */
if (curr != null && curr.val == target) {
return true;
}
return false;
}
public void add(int num) {
SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
Arrays.fill(update, head);
SkiplistNode curr = this.head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 num 的元素*/
while (curr.forward[i] != null && curr.forward[i].val < num) {
curr = curr.forward[i];
}
update[i] = curr;
}
int lv = randomLevel();
level = Math.max(level, lv);
SkiplistNode newNode = new SkiplistNode(num, lv);
for (int i = 0; i < lv; i++) {
/* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
}
public boolean erase(int num) {
SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
SkiplistNode curr = this.head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 num 的元素*/
while (curr.forward[i] != null && curr.forward[i].val < num) {
curr = curr.forward[i];
}
update[i] = curr;
}
curr = curr.forward[0];
/* 如果值不存在则返回 false */
if (curr == null || curr.val != num) {
return false;
}
for (int i = 0; i < level; i++) {
if (update[i].forward[i] != curr) {
break;
}
/* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */
update[i].forward[i] = curr.forward[i];
}
/* 更新当前的 level */
while (level > 1 && head.forward[level - 1] == null) {
level--;
}
return true;
}
private int randomLevel() {
int lv = 1;
/* 随机生成 lv */
while (random.nextDouble() < P_FACTOR && lv < MAX_LEVEL) {
lv++;
}
return lv;
}
}
class SkiplistNode {
int val;
SkiplistNode[] forward;
public SkiplistNode(int val, int maxLevel) {
this.val = val;
this.forward = new SkiplistNode[maxLevel];
}
}
/**
* Your Skiplist object will be instantiated and called as such:
* Skiplist obj = new Skiplist();
* boolean param_1 = obj.search(target);
* obj.add(num);
* boolean param_3 = obj.erase(num);
*/
golang 解法, 执行用时: 68 ms, 内存消耗: 11.3 MB, 提交时间: 2023-04-19 10:15:50
const maxLevel = 32
const pFactor = 0.25
type SkiplistNode struct {
val int
forward []*SkiplistNode
}
type Skiplist struct {
head *SkiplistNode
level int
}
func Constructor() Skiplist {
return Skiplist{&SkiplistNode{-1, make([]*SkiplistNode, maxLevel)}, 0}
}
func (Skiplist) randomLevel() int {
lv := 1
for lv < maxLevel && rand.Float64() < pFactor {
lv++
}
return lv
}
func (s *Skiplist) Search(target int) bool {
curr := s.head
for i := s.level - 1; i >= 0; i-- {
// 找到第 i 层小于且最接近 target 的元素
for curr.forward[i] != nil && curr.forward[i].val < target {
curr = curr.forward[i]
}
}
curr = curr.forward[0]
// 检测当前元素的值是否等于 target
return curr != nil && curr.val == target
}
func (s *Skiplist) Add(num int) {
update := make([]*SkiplistNode, maxLevel)
for i := range update {
update[i] = s.head
}
curr := s.head
for i := s.level - 1; i >= 0; i-- {
// 找到第 i 层小于且最接近 num 的元素
for curr.forward[i] != nil && curr.forward[i].val < num {
curr = curr.forward[i]
}
update[i] = curr
}
lv := s.randomLevel()
s.level = max(s.level, lv)
newNode := &SkiplistNode{num, make([]*SkiplistNode, lv)}
for i, node := range update[:lv] {
// 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点
newNode.forward[i] = node.forward[i]
node.forward[i] = newNode
}
}
func (s *Skiplist) Erase(num int) bool {
update := make([]*SkiplistNode, maxLevel)
curr := s.head
for i := s.level - 1; i >= 0; i-- {
// 找到第 i 层小于且最接近 num 的元素
for curr.forward[i] != nil && curr.forward[i].val < num {
curr = curr.forward[i]
}
update[i] = curr
}
curr = curr.forward[0]
// 如果值不存在则返回 false
if curr == nil || curr.val != num {
return false
}
for i := 0; i < s.level && update[i].forward[i] == curr; i++ {
// 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳
update[i].forward[i] = curr.forward[i]
}
// 更新当前的 level
for s.level > 1 && s.head.forward[s.level-1] == nil {
s.level--
}
return true
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
/**
* Your Skiplist object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Search(target);
* obj.Add(num);
* param_3 := obj.Erase(num);
*/
python3 解法, 执行用时: 208 ms, 内存消耗: 22.9 MB, 提交时间: 2023-04-19 10:15:25
MAX_LEVEL = 32
P_FACTOR = 0.25
def random_level() -> int:
lv = 1
while lv < MAX_LEVEL and random.random() < P_FACTOR:
lv += 1
return lv
class SkiplistNode:
__slots__ = 'val', 'forward'
def __init__(self, val: int, max_level=MAX_LEVEL):
self.val = val
self.forward = [None] * max_level
class Skiplist:
def __init__(self):
self.head = SkiplistNode(-1)
self.level = 0
def search(self, target: int) -> bool:
curr = self.head
for i in range(self.level - 1, -1, -1):
# 找到第 i 层小于且最接近 target 的元素
while curr.forward[i] and curr.forward[i].val < target:
curr = curr.forward[i]
curr = curr.forward[0]
# 检测当前元素的值是否等于 target
return curr is not None and curr.val == target
def add(self, num: int) -> None:
update = [self.head] * MAX_LEVEL
curr = self.head
for i in range(self.level - 1, -1, -1):
# 找到第 i 层小于且最接近 num 的元素
while curr.forward[i] and curr.forward[i].val < num:
curr = curr.forward[i]
update[i] = curr
lv = random_level()
self.level = max(self.level, lv)
new_node = SkiplistNode(num, lv)
for i in range(lv):
# 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
def erase(self, num: int) -> bool:
update = [None] * MAX_LEVEL
curr = self.head
for i in range(self.level - 1, -1, -1):
# 找到第 i 层小于且最接近 num 的元素
while curr.forward[i] and curr.forward[i].val < num:
curr = curr.forward[i]
update[i] = curr
curr = curr.forward[0]
if curr is None or curr.val != num: # 值不存在
return False
for i in range(self.level):
if update[i].forward[i] != curr:
break
# 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳
update[i].forward[i] = curr.forward[i]
# 更新当前的 level
while self.level > 1 and self.head.forward[self.level - 1] is None:
self.level -= 1
return True
# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)
