上次编辑到这里，代码来自缓存 点击恢复默认模板
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);
*/
php 解法, 执行用时: 5 ms, 内存消耗: 31 MB, 提交时间: 2025-02-23 10:09:16
class Skiplist {
/**
*/
function __construct() {
$this->map = [];
}
/**
* @param Integer $target
* @return Boolean
*/
function search($target) {
return isset($this->map[$target]);
}
/**
* @param Integer $num
* @return NULL
*/
function add($num) {
$this->map[$num]++;
}
/**
* @param Integer $num
* @return Boolean
*/
function erase($num) {
if (isset($this->map[$num])) {
$this->map[$num]--;
if (empty($this->map[$num])) {
unset($this->map[$num]);
}
return true;
}
return false;
}
}
/**
* Your Skiplist object will be instantiated and called as such:
* $obj = Skiplist();
* $ret_1 = $obj->search($target);
* $obj->add($num);
* $ret_3 = $obj->erase($num);
*/
javascript 解法, 执行用时: 42 ms, 内存消耗: 70.3 MB, 提交时间: 2025-02-23 10:06:48
const MAX_LEVEL = 32;
const P_FACTOR = 0.25;
var Skiplist = function() {
this.head = new SkiplistNode(-1, MAX_LEVEL);
this.level = 0;
};
Skiplist.prototype.search = function(target) {
let curr = this.head;
for (let i = this.level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 target 的元素*/
while (curr.forward[i] && curr.forward[i].val < target) {
curr = curr.forward[i];
}
}
curr = curr.forward[0];
/* 检测当前元素的值是否等于 target */
if (curr && curr.val === target) {
return true;
}
return false;
};
Skiplist.prototype.add = function(num) {
const update = new Array(MAX_LEVEL).fill(this.head);
let curr = this.head;
for (let i = this.level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 num 的元素*/
while (curr.forward[i] && curr.forward[i].val < num) {
curr = curr.forward[i];
}
update[i] = curr;
}
const lv = randomLevel();
this.level = Math.max(this.level, lv);
const newNode = new SkiplistNode(num, lv);
for (let i = 0; i < lv; i++) {
/* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
};
Skiplist.prototype.erase = function(num) {
const update = new Array(MAX_LEVEL).fill(0);
let curr = this.head;
for (let i = this.level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 num 的元素*/
while (curr.forward[i] && curr.forward[i].val < num) {
curr = curr.forward[i];
}
update[i] = curr;
}
curr = curr.forward[0];
/* 如果值不在存则返回 false */
if (!curr || curr.val !== num) {
return false;
}
for (let i = 0; i < this.level; i++) {
if (update[i].forward[i] !== curr) {
break;
}
/* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */
update[i].forward[i] = curr.forward[i];
}
/* 更新当前的 level */
while (this.level > 1 && !this.head.forward[this.level - 1]) {
this.level--;
}
return true;
};
const randomLevel = () => {
let lv = 1;
/* 随机生成 lv */
while (Math.random() < P_FACTOR && lv < MAX_LEVEL) {
lv++;
}
return lv;
}
class SkiplistNode {
constructor(val, maxLevel) {
this.val = val;
this.forward = new Array(maxLevel).fill(0);
}
}
/**
* Your Skiplist object will be instantiated and called as such:
* var obj = new Skiplist()
* var param_1 = obj.search(target)
* obj.add(num)
* var param_3 = obj.erase(num)
*/
cpp 解法, 执行用时: 38 ms, 内存消耗: 44.4 MB, 提交时间: 2025-02-23 10:06:12
constexpr int MAX_LEVEL = 32;
constexpr double P_FACTOR = 0.25;
struct SkiplistNode {
int val;
vector<SkiplistNode *> forward;
SkiplistNode(int _val, int _maxLevel = MAX_LEVEL) : val(_val), forward(_maxLevel, nullptr) {
}
};
class Skiplist {
private:
SkiplistNode * head;
int level;
mt19937 gen{random_device{}()};
uniform_real_distribution<double> dis;
public:
Skiplist(): head(new SkiplistNode(-1)), level(0), dis(0, 1) {
}
bool search(int target) {
SkiplistNode *curr = this->head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 target 的元素*/
while (curr->forward[i] && curr->forward[i]->val < target) {
curr = curr->forward[i];
}
}
curr = curr->forward[0];
/* 检测当前元素的值是否等于 target */
if (curr && curr->val == target) {
return true;
}
return false;
}
void add(int num) {
vector<SkiplistNode *> update(MAX_LEVEL, head);
SkiplistNode *curr = this->head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 num 的元素*/
while (curr->forward[i] && curr->forward[i]->val < num) {
curr = curr->forward[i];
}
update[i] = curr;
}
int lv = randomLevel();
level = 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;
}
}
bool erase(int num) {
vector<SkiplistNode *> update(MAX_LEVEL, nullptr);
SkiplistNode *curr = this->head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 num 的元素*/
while (curr->forward[i] && curr->forward[i]->val < num) {
curr = curr->forward[i];
}
update[i] = curr;
}
curr = curr->forward[0];
/* 如果值不存在则返回 false */
if (!curr || 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];
}
delete curr;
/* 更新当前的 level */
while (level > 1 && head->forward[level - 1] == nullptr) {
level--;
}
return true;
}
int randomLevel() {
int lv = 1;
/* 随机生成 lv */
while (dis(gen) < P_FACTOR && lv < MAX_LEVEL) {
lv++;
}
return lv;
}
};
/**
* 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)
