【Day 91 】2021-12-09 - 1206. 设计跳表 #110
Comments
思路:需要实现以下 3 个函数:
代码:实现语言: C++ struct Node {
Node *right, *down;
int val;
Node(Node* right, Node* down, int val): right(right), down(down), val(val) {}
};
class Skiplist {
Node* head;
vector<Node*> insertPoints;
public:
Skiplist() {
head = new Node(nullptr, nullptr, 0);
}
bool search(int target) {
Node* p = head;
while (p)
{
while (p->right && p->right->val < target) /* 找当前层的1个适合的区间: 如果p->right变成NULL或target <= p->right结点的值时说明找到合适位置了, 否则继续右移 */
p = p->right;
if (!p->right || p->right->val > target) // 没找到, 就继续到下1层去找
p = p->down;
else
return true;
}
return false;
}
void add(int num)
{
insertPoints.clear();
Node* p = head;
while (p)
{
while (p->right && p->right->val < num)
p = p->right;
insertPoints.push_back(p);
p = p->down;
}
Node* downNode = nullptr;
bool insertUp = true;
while (insertUp && insertPoints.size())
{
Node* ins = insertPoints.back();
insertPoints.pop_back();
ins->right = new Node(ins->right, downNode, num);
downNode = ins->right;
insertUp = (rand() & 1) == 0; // 50% 的可能性
}
if (insertUp) // 创建一个新的layer
{
head = new Node(new Node(nullptr, downNode, num), head, 0);
}
}
bool erase(int num)
{
Node* p = head;
bool seen = false; // 跳表中是否存在要删的值
while (p)
{
while (p->right && p->right->val < num)
p = p->right;
if (!p->right || p->right->val > num) // 没找到要删的值, 就继续到下1层去找
p = p->down;
else /* 找到了要删的值, 就删除这个结点 */
{
seen = true;
p->right = p->right->right;
p = p->down;
}
}
return seen;
}
};复杂度分析:跳表查询、插入、删除的复杂度均为:
跳表的时间复杂度和空间复杂度不是很好分析。由于时间复杂度 = 索引的高度 * 平均每层索引遍历元素的个数，而高度大概为 log n，并且每层遍历的元素是常数，因此时间复杂度为 log n。 空间复杂度就等同于索引节点的个数，以每两个节点建立一个索引为例，大概是 n/2 + n/4 + n/8 + … + 8 + 4 + 2 ，因此空间复杂度是 O(n)。 |
|
复制题解学习 } |
class Node:
__slots__ = 'val', 'levels'
def __init__(self, val, levels):
self.val = val
self.levels = [None] * levels
class Skiplist(object):
def __init__(self):
self.head = Node(-1, 16)
def _iter(self, num):
cur = self.head
for level in range(15, -1, -1):
while True:
future = cur.levels[level]
if future and future.val < num:
cur = future
else:
break
yield cur, level
def search(self, target):
for prev, level in self._iter(target):
pass
cur = prev.levels[0]
return cur and cur.val == target
def add(self, num):
nodelvls = min(16, 1 + int(math.log2(1.0 / random.random())))
node = Node(num, nodelvls)
for cur, level in self._iter(num):
if level < nodelvls:
future = cur.levels[level]
cur.levels[level] = node
node.levels[level] = future
def erase(self, num):
ans = False
for cur, level in self._iter(num):
future = cur.levels[level]
if future and future.val == num:
ans = True
cur.levels[level] = future.levels[level]
return ans |
思路
Java Codeclass Skiplist {
ListNode head;
Random random = new Random();
public Skiplist() {
head = new ListNode(-1, null, null);
}
public boolean search(int target) {
ListNode p = head;
while (p != null) {
while (p.right != null && p.right.val < target) {
p = p.right;
}
if (p.right != null && p.right.val == target) {
return true;
}
p = p.down;
}
return false;
}
public void add(int num) {
ListNode p = head;
Deque<ListNode> stack = new ArrayDeque();
while (p != null) {
while (p.right != null && p.right.val < num) {
p = p.right;
}
stack.push(p);
p = p.down;
}
boolean insert = true;
ListNode down = null;
while (insert && !stack.isEmpty()) {
p = stack.pop();
p.right = new ListNode(num, p.right, down);
insert = insert && random.nextInt(2) == 0;
down = p.right;
}
if (insert) {
this.head = new ListNode(-1, null, head);
}
}
public boolean erase(int num) {
ListNode p = head;
boolean found = false;
while (p != null) {
while (p.right != null && p.right.val < num) {
p = p.right;
}
if (p.right != null && p.right.val == num) {
p.right = p.right.right;
found = true;
}
p = p.down;
}
return found;
}
private static class ListNode {
int val;
ListNode right;
ListNode down;
public ListNode(int val, ListNode right, ListNode down) {
this.val = val;
this.right = right;
this.down = down;
}
}
}时间&空间
|
|
class Node: class Skiplist: |
Problemhttps://leetcode.com/problems/design-skiplist/ Note
Solutionclass Skiplist {
private static final double P = 0.25d;
private static final int MAX_LEVEL = 32;
private Node head = new Node(null, MAX_LEVEL);
private int curLevel = 1;
public Skiplist() {
}
public boolean search(int target) {
// search from head from upper level
Node searchNode = head;
for(int i = curLevel - 1; i >= 0; i--){
searchNode = findClosest(searchNode, i, target);
if(searchNode.next[i] != null && searchNode.next[i].val == target){
return true;
}
}
return false;
}
public void add(int num) {
int level = randomLevel();
Node newNode = new Node(num, level);
Node updateNode = head; // start from head, and find the closest node to the new node
// process all the existing levels
for(int i = curLevel - 1; i >= 0; i--){
updateNode = findClosest(updateNode, i, num);// find and update the closest node for each level
if(i < level){ // add newNode to the current level only if i < level
if(updateNode.next[i] == null){
updateNode.next[i] = newNode;
}else{
Node temp = updateNode.next[i];
updateNode.next[i] = newNode;
newNode.next[i] = temp;
}
}
}
// if the random level is > curLevel, put the new node in the new levels, and increase the curLevel
if(level > curLevel){ //
for(int i = curLevel; i < level; i++){
head.next[i] = newNode;
}
curLevel = level;
}
}
public boolean erase(int num) {
// search from head from upper level
Node searchNode = head;
boolean flag = false;
for(int i = curLevel - 1; i >= 0; i--){
searchNode = findClosest(searchNode, i, num);
if(searchNode.next[i] != null && searchNode.next[i].val == num){
searchNode.next[i] = searchNode.next[i].next[i];
flag = true; // shouldn't return immediately, need to erase the node at every level
}
}
return flag;
}
// start from the given node, find the closest node at the given level, so that the given val is > the closest node's val and the given val is <= node's next val
private Node findClosest(Node node, int levelIndex, int val){
while(levelIndex < node.next.length && node.next[levelIndex] != null && val > node.next[levelIndex].val){
node = node.next[levelIndex];
}
return node;
}
// get a random level
private int randomLevel(){
int level = 1;
while(Math.random() < P && level < MAX_LEVEL){
level++;
}
return level;
}
}
class Node{
Integer val;
Node[] next;
public Node(Integer val, int size){
this.val = val;
this.next = new Node[size];
}
}
/**
* 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);
*/Complexity
|
class Solution:
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
m = {}
for i in barcodes:
if i not in m:
m[i] = 1
else:
m[i] += 1
index = [i for i in range(0, len(barcodes), 2)] + [i for i in range(1, len(barcodes), 2)]
res = [-1 for _ in barcodes]
i = 0
while len(m) > 0:
k = max(m, key=m.get)
for j in range(m[k]):
res[index[i]] = k
i += 1
del m[k]
return res
|
const (
maxLevel = 16
maxRand = 65535.0
)
func randLevel() int{
return maxLevel - int(math.Log2(1.0+maxRand*rand.Float64()))
}
type skipNode struct{
value int
right *skipNode
down *skipNode
}
type Skiplist struct {
head *skipNode
}
func Constructor() Skiplist {
left := make([]*skipNode,maxLevel)
right := make([]*skipNode,maxLevel)
for i:=0;i<maxLevel;i++{
left[i] = &skipNode{-1,nil,nil}
right[i] = &skipNode{20001,nil,nil}
}
for i:= maxLevel-2;i>=0;i--{
left[i].right = right[i]
left[i].down = left[i+1]
right[i].down = right[i+1]
}
left[maxLevel-1].right = right[maxLevel-1]
return Skiplist{left[0]}
}
func (this *Skiplist) Search(target int) bool {
node := this.head
for node != nil{
if node.right.value > target{
node = node.down
}else if node.right.value < target{
node = node.right
}else{
return true
}
}
return false
}
func (this *Skiplist) Add(num int) {
prev := make([]*skipNode,maxLevel)
i := 0
node := this.head
for node != nil{
if node.right.value >= num{
prev[i] = node
i++
node = node.down
}else{
node = node.right
}
}
n := randLevel()
arr := make([]*skipNode,n)
t := &skipNode{-1,nil,nil}
for i,a := range arr{
p := prev[maxLevel-n+i]
a = &skipNode{num,p.right,nil}
p.right = a
t.down = a
t = a
}
}
func (this *Skiplist) Erase(num int) bool {
node := this.head
out := false
for node != nil{
if node.right.value > num{
node = node.down
}else if node.right.value < num{
node = node.right
}else{
out = true
node.right = node.right.right
node = node.down
}
}
return out
}
/**
* 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);
*/ |
|
思路:
复杂度分析:
代码(C++): struct SkipNode {
int val;
SkipNode *right, *down;
SkipNode(int v, SkipNode* r, SkipNode* d) : val(v), right(r), down(d) {};
};
class Skiplist {
public:
Skiplist() {
head = nullptr;
layer = 0;
}
bool search(int target) {
SkipNode* cur = head;
while (cur) {
while (cur->right && cur->right->val < target)
cur = cur->right;
if (cur->right && cur->right->val == target) return true;
cur = cur->down;
}
return false;
}
void add(int num) {
int rlayer = 1;
while (rlayer <= layer && (rand() & 1) == 0) ++rlayer;
if (rlayer > layer) {
layer = rlayer;
head = new SkipNode(num, nullptr, head);
}
SkipNode *cur = head, *last = nullptr;
for (int l = layer; l >= 1; --l) {
while (cur->right && cur->right->val < num) cur = cur->right;
if (l <= rlayer) {
cur->right = new SkipNode(num, cur->right, nullptr);
if (last)
last->down = cur->right;
last = cur->right;
}
cur = cur->down;
}
}
bool erase(int num) {
SkipNode *cur = head;
bool seen = false;
for (int l = layer; l >= 1; --l) {
while (cur->right && cur->right->val < num) cur = cur->right;
if (cur->right && cur->right->val == num) {
seen = true;
SkipNode* tmp = cur->right;
cur->right = tmp->right;
delete(tmp);
}
cur = cur->down;
}
return seen;
}
private:
SkipNode *head;
int layer;
};
/**
* 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);
*/ |
思路大致了解一下实现方式 代码class Skiplist {
private int MAX_LEVEL = 30;
private Node head;
private int curMaxLevel = 1;
public Skiplist() {
head = new Node(-1, MAX_LEVEL);
curMaxLevel = 1;
}
public boolean search(int target) {
for (int i=curMaxLevel-1; i>=0; i--) {
Node node = findClosest(head, i, target);
if (node.next[i] != null && node.next[i].value == target) {
return true;
}
}
return false;
}
public void add(int num) {
int level = randomLevel();
Node newNode = new Node(num, level);
for (int i=curMaxLevel-1; i>=0; i--) {
Node node = findClosest(head, i, num);
if (i < level) {
Node nextNode = node.next[i];
node.next[i] = newNode;
newNode.next[i] = nextNode;
}
}
if (level > curMaxLevel) {
for (int i=curMaxLevel; i<level; i++) {
head.next[i] = newNode;
}
curMaxLevel = level;
}
}
public boolean erase(int num) {
boolean found = false;
for (int i=curMaxLevel-1; i>=0; i--) {
Node node = findClosest(head, i, num);
if (node.next[i] != null && node.next[i].value == num) {
node.next[i] = node.next[i].next[i];
found = true;
}
}
return found;
}
private Node findClosest(Node node, int levelIndex, int target) {
while ((node.next[levelIndex] != null && node.next[levelIndex].value < target)) {
node = node.next[levelIndex];
}
return node;
}
private int randomLevel() {
double DEFAULT_P_FACTOR = 0.25;
int level = 1;
while(Math.random() < DEFAULT_P_FACTOR && level < MAX_LEVEL) {
level++;
}
return level;
// return new Random().nextInt(MAX_LEVEL + 1);
}
class Node {
int value;
Node[] next;
public Node(int value, int size) {
this.value = value;
this.next = new Node[size];
}
}
} |
link:https://leetcode.com/problems/design-skiplist/ 代码 Javascriptconst Node = function (val = -1, right = null, down = null) {
this.val = val;
this.right = right;
this.down = down;
}
const Skiplist = function() {
this.head = new Node() // dummy head
};
/**
* @param {number} target
* @return {boolean}
*/
Skiplist.prototype.search = function(target) {
var node = this.head;
while (node) {
while (node.right && node.right.val < target) {
node = node.right;
}
if (node.right && node.right.val === target) {
return true;
}
node = node.down;
}
return false;
};
/**
* @param {number} num
* @return {void}
*/
Skiplist.prototype.add = function(num) {
var pathlist = [];
var node = this.head;
while (node) {
while (node.right && node.right.val < num) {
node = node.right;
}
pathlist.push(node);
node = node.down;
}
var insertUp = true;
var downNode = null;
while (insertUp && pathlist.length !== 0) {
var insertNode = pathlist.pop();
insertNode.right = new Node(num, insertNode.right, downNode);
downNode = insertNode.right;
insertUp = (Math.random() * 10 & 1) === 0;
}
if (insertUp) {
this.head = new Node(-1, null, this.head);
}
};
/**
* @param {number} num
* @return {boolean}
*/
Skiplist.prototype.erase = function(num) {
var node = this.head;
var found = false;
while (node) {
while (node.right && node.right.val < num) {
node = node.right;
}
if (!node.right || node.right.val > num) {
node = node.down;
} else {
found = true;
node.right = node.right.right;
node = node.down;
}
}
return found;
}; |
开始刷题题目简介【Day 91 】2021-12-09 - 1206. 设计跳表题目思路
题目代码代码块class Skiplist {
private:
SkipListNode *head, *tail;
int level, length;
public:
static constexpr int MAXL = 32;
static constexpr int P = 4;
static constexpr int S = 0xFFFF;
static constexpr int PS = S / 4;
Skiplist() {
level = length = 0;
tail = new SkipListNode(INT_MAX, 0);
head = new SkipListNode(INT_MAX);
for (int i = 0; i < MAXL; ++i) {
head->level[i] = tail;
}
}
SkipListNode* find(int val) {
SkipListNode *p = head;
for (int i = level - 1; i >= 0; --i) {
while (p->level[i] && p->level[i]->val < val) {
p = p->level[i];
}
}
p = p->level[0];
return p;
}
bool search(int target) {
SkipListNode *p = find(target);
return p->val == target;
}
void add(int val) {
vector<SkipListNode *> update(MAXL);
SkipListNode *p = head;
for (int i = level - 1; i >= 0; --i) {
while (p->level[i] && p->level[i]->val < val) {
p = p->level[i];
}
update[i] = p;
}
int lv = randomLevel();
if (lv > level) {
lv = ++level;
update[lv - 1] = head;
}
SkipListNode *newNode = new SkipListNode(val, lv);
for (int i = lv - 1; i >= 0; --i) {
p = update[i];
newNode->level[i] = p->level[i];
p->level[i] = newNode;
}
++length;
}
bool erase(int val) {
vector<SkipListNode *> update(MAXL + 1);
SkipListNode *p = head;
for (int i = level - 1; i >= 0; --i) {
while (p->level[i] && p->level[i]->val < val) {
p = p->level[i];
}
update[i] = p;
}
p = p->level[0];
if (p->val != val) return false;
for (int i = 0; i < level; ++i) {
if (update[i]->level[i] != p) {
break;
}
update[i]->level[i] = p->level[i];
}
while (level > 0 && head->level[level - 1] == tail) --level;
--length;
return true;
}
int randomLevel() {
int lv = 1;
while (lv < MAXL && (rand() & S) < PS) ++lv;
return lv;
}
};
复杂度
|
IdeaRefer to Solutions in Leet Code Code:class Node:
__slots__ = 'val', 'levels'
def __init__(self, val, levels):
self.val = val
self.levels = [None] * levels
class Skiplist(object):
def __init__(self):
self.head = Node(-1, 16)
def _iter(self, num):
cur = self.head
for level in range(15, -1, -1):
while True:
future = cur.levels[level]
if future and future.val < num:
cur = future
else:
break
yield cur, level
def search(self, target):
for prev, level in self._iter(target):
pass
cur = prev.levels[0]
return cur and cur.val == target
def add(self, num):
nodelvls = min(16, 1 + int(math.log2(1.0 / random.random())))
node = Node(num, nodelvls)
for cur, level in self._iter(num):
if level < nodelvls:
future = cur.levels[level]
cur.levels[level] = node
node.levels[level] = future
def erase(self, num):
ans = False
for cur, level in self._iter(num):
future = cur.levels[level]
if future and future.val == num:
ans = True
cur.levels[level] = future.levels[level]
return ans |
1206. Design Skiplisthttps://leetcode.com/problems/design-skiplist/ Topics-skiplist 思路-skiplist 代码 Pythonclass Node:
__slots__ = 'val', 'levels'
def __init__(self, val, levels):
self.val = val
self.levels = [None] * levels
class Skiplist(object):
def __init__(self):
self.head = Node(-1, 16)
def _iter(self, num):
cur = self.head
for level in range(15, -1, -1):
while True:
future = cur.levels[level]
if future and future.val < num:
cur = future
else:
break
yield cur, level
def search(self, target):
for prev, level in self._iter(target):
pass
cur = prev.levels[0]
return cur and cur.val == target
def add(self, num):
nodelvls = min(16, 1 + int(math.log2(1.0 / random.random())))
node = Node(num, nodelvls)
for cur, level in self._iter(num):
if level < nodelvls:
future = cur.levels[level]
cur.levels[level] = node
node.levels[level] = future
def erase(self, num):
ans = False
for cur, level in self._iter(num):
future = cur.levels[level]
if future and future.val == num:
ans = True
cur.levels[level] = future.levels[level]
return ans
# 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)复杂度分析时间复杂度： O(log(N)) |
class Skiplist {
/**
* 最大层数
*/
private static int DEFAULT_MAX_LEVEL = 32;
/**
* 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1
*/
private static double DEFAULT_P_FACTOR = 0.25;
Node head = new Node(null,DEFAULT_MAX_LEVEL); //头节点
int currentLevel = 1; //表示当前nodes的实际层数，它从1开始
public Skiplist() {
}
public boolean search(int target) {
Node searchNode = head;
for (int i = currentLevel-1; i >=0; i--) {
searchNode = findClosest(searchNode, i, target);
if (searchNode.next[i]!=null && searchNode.next[i].value == target){
return true;
}
}
return false;
}
/**
*
* @param num
*/
public void add(int num) {
int level = randomLevel();
Node updateNode = head;
Node newNode = new Node(num,level);
// 计算出当前num 索引的实际层数，从该层开始添加索引
for (int i = currentLevel-1; i>=0; i--) {
//找到本层最近离num最近的list
updateNode = findClosest(updateNode,i,num);
if (i<level){
if (updateNode.next[i]==null){
updateNode.next[i] = newNode;
}else{
Node temp = updateNode.next[i];
updateNode.next[i] = newNode;
newNode.next[i] = temp;
}
}
}
if (level > currentLevel){ //如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode
for (int i = currentLevel; i < level; i++) {
head.next[i] = newNode;
}
currentLevel = level;
}
}
public boolean erase(int num) {
boolean flag = false;
Node searchNode = head;
for (int i = currentLevel-1; i >=0; i--) {
searchNode = findClosest(searchNode, i, num);
if (searchNode.next[i]!=null && searchNode.next[i].value == num){
//找到该层中该节点
searchNode.next[i] = searchNode.next[i].next[i];
flag = true;
continue;
}
}
return flag;
}
/**
* 找到level层 value 大于node 的节点
* @param node
* @param levelIndex
* @param value
* @return
*/
private Node findClosest(Node node,int levelIndex,int value){
while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
node = node.next[levelIndex];
}
return node;
}
/**
* 随机一个层数
*/
private static int randomLevel(){
int level = 1;
while (Math.random()<DEFAULT_P_FACTOR && level<DEFAULT_MAX_LEVEL){
level ++ ;
}
return level;
}
class Node{
Integer value;
Node[] next;
public Node(Integer value,int size) {
this.value = value;
this.next = new Node[size];
}
@Override
public String toString() {
return String.valueOf(value);
}
}
} |
题目https://leetcode-cn.com/problems/design-skiplist/ 思路SkipList python3class Node:
def __init__(self, val = 0):
self.val = val
self.right = None
self.down = None
class Skiplist:
def __init__(self):
left = [Node(-1) for _ in range(16)]
right = [Node(20001) for _ in range(16)]
for i in range(15):
left[i].right = right[i]
left[i].down = left[i + 1]
right[i].down = right[i + 1]
left[-1].right = right[-1]
self.head = left[0]
def search(self, target: int) -> bool:
cur = self.head
while cur:
if cur.right.val > target:
cur = cur.down
elif cur.right.val < target:
cur = cur.right
else:
return True
return False
def add(self, num: int) -> None:
cur = self.head
stack = []
while cur:
if cur.right.val >= num:
stack.append(cur)
cur = cur.down
else:
cur = cur.right
pre = None
while stack:
cur = stack.pop()
node = Node(num)
node.right = cur.right
cur.right = node
if pre:
node.down = pre
pre = node
if random.randint(0, 1):
break
def erase(self, num: int) -> bool:
cur = self.head
is_removed = False
while cur:
if cur.right.val >= num:
if cur.right.val == num:
is_removed = True
cur.right = cur.right.right
cur = cur.down
else:
cur = cur.right
return is_removed
# 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)复杂度分析
相关题目
|
【day91】题目地址（1206. 设计跳表）https://leetcode-cn.com/problems/design-skiplist/ # 最大级深maxLevl=16，power=2分链表，随机数的上限maxRand
maxLevel = 16
power = 2
maxRand = power ** maxLevel - 1
# 随机函数，这里就相当于[1 ... 65535]取随机，然后再对2取对数，可保证插入深度在[1 ... 16]这些数字里呈对数分布
randLevel = lambda: maxLevel - int(math.log(random.randint(1, maxRand), power))
# 三个属性，跳表本体的值，向右的指针，向下的指针
class SkipNode:
def __init__(self, value):
self.value = value
self.right = None
self.down = None
class Skiplist:
def __init__(self):
# 初始化左右正负无穷墙壁
left = [SkipNode(-float('inf')) for _ in range(maxLevel)]
right = [SkipNode(float('inf')) for _ in range(maxLevel)]
# 把墙壁交联在一起
for i in range(maxLevel - 1):
left[i].right = right[i]
left[i].down = left[i + 1]
right[i].down = right[i + 1]
# 最后一层单独处理，只有向右指向，没有向下指向
left[-1].right = right[-1]
# 跳表初始指针为左壁的首元素
self.head = left[0]
def search(self, target: int) -> bool:
# 从初始指针开始进行跳跃迭代，找不到的node迟早为None，跳出循环自动返回False
node = self.head
while node:
if node.right.value > target:
node = node.down
elif node.right.value < target:
node = node.right
else:
return True
return False
def add(self, num: int) -> None:
# 用prev数组存储往下跳跃前的跳表指针，方便之后插入指针时前后交联，免去双向指针处理
prev = []
# 原理依旧是指针迭代
node = self.head
while node:
# 碰到右边大于等于自己时就往下跳，帮助prev生成完整的指针数组
if node.right.value >= num:
prev.append(node)
node = node.down
else:
node = node.right
# 待插入的指针数组，长度按概率进行随机
arr = [SkipNode(num) for _ in range(randLevel())]
# 用zip把prev后续的元素与新的指针数组交联在一次即可完成跳表插入
t = SkipNode(None)
for p, a in zip(prev[maxLevel - len(arr): ], arr):
a.right = p.right
p.right = a
t.down = a
t = a
def erase(self, num: int) -> bool:
# ans为输出标志，erase的结构和search结构类似，依旧是指针迭代
ans = False
node = self.head
while node:
if node.right.value > num:
node = node.down
elif node.right.value < num:
node = node.right
else:
# 存在相等时就修改输出标志
ans = True
# 删除node.right的在跳表中的关系
node.right = node.right.right
node = node.down
return ans复杂度分析：
|
thought看的解答实现 codeclass Node:
def __init__(self, val = 0):
self.val = val
self.right = None
self.down = None
class Skiplist:
def __init__(self):
left = [Node(-1) for _ in range(16)]
right = [Node(20001) for _ in range(16)]
for i in range(15):
left[i].right = right[i]
left[i].down = left[i + 1]
right[i].down = right[i + 1]
left[-1].right = right[-1]
self.head = left[0]
def search(self, target: int) -> bool:
cur = self.head
while cur:
if cur.right.val > target:
cur = cur.down
elif cur.right.val < target:
cur = cur.right
else:
return True
return False
def add(self, num: int) -> None:
cur = self.head
stack = []
while cur:
if cur.right.val >= num:
stack.append(cur)
cur = cur.down
else:
cur = cur.right
pre = None
while stack:
cur = stack.pop()
node = Node(num)
node.right = cur.right
cur.right = node
if pre: node.down = pre
pre = node
if random.randint(0, 1): break
def erase(self, num: int) -> bool:
cur = self.head
is_removed = False
while cur:
if cur.right.val >= num:
if cur.right.val == num:
is_removed = True
cur.right = cur.right.right
cur = cur.down
else:
cur = cur.right
return is_removedComplexityTime O(lgn) Space O(n) |
思路
从最上面一层开始, 每次一直向右移动直到 cur.next.num < target 为止, 即每次都找到每一层的最大的小于 num 的数字 判断 下一个数字是否 等于 num, 如果等于 返回 True 否则 指针移动到下面一行 skiplist 上继续循环 最后如果跳出循环了还没找到, 代表已经搜索到最后一行下面了, 所以这个数字不存在 skiplist 中, 返回 False 跟 search 思路相同 从最上面一层开始, 每次一直向右移动直到 cur.next.num < target 为止, 即每次都找到每一层的最大的小于 num 的数字 判断 下一个数字是否 等于 num, 如果等于 标记找到 found = True, 并且将下一个数字移除 之后指针移动到下面一行 skiplist 上继续循环 最后返回 found 从最上面一层开始, 每次一直向右移动直到 cur.next.num < target 为止, 即每次都找到每一层的最大的小于 num 的数字 将每一层最大的小于 num 的数字都添加到数组 prev 中 initialize down_node = None, build_up = True 分别代表这个当前如果要添加节点, 下面的节点的pointer 以及此时是否要 build_up 继续向上添加这个节点 因为我们是从最底层开始, 所以 down_node = None 因为底下没有别的 skiplist 了, build_up = True 因为最底层是一定要添加这个数字的 添加节点时将 prev_node.pop() 取出当前最后一层的添加节点的前驱节点, 然后将节点添加到前驱节点后面并跟后面的节点相连接, 并且也跟 down_node 相连接 down_node 更新为 prev_node.nxt 即为刚刚添加过的新的节点 build_up 更新为 random.randint(0,1)==0 每次这个节点继续向上添加下一层的概率为 1/2 最后如果跳出循环后 build_up 还是 True, 代表可以继续网上建一层, 那么添加新的 dummy head node 并且将 self.head 更新为新的节点, 原来的 head 更新为 新 head 的 down 节点 因为每次向上 build_up 的概率为 1/2, 所以最后一层 d 概率为 1, d-1 层概率为 1/2, ... 1 层概率为 (1/2)^(d-1), 从 1 层继续向上建一新的一层的概率为 (1/2)^(d), 可以看出当数据规模变大的时候, 有概率添加新的 skiplist 层, 来保持 skiplist 的 property import random
class Node:
def __init__(self, num, nxt=None, down=None):
self.num = num
self.nxt = nxt
self.down = down
class Skiplist:
def __init__(self):
# create head pointing to dummy node
self.head = Node(-1)
def search(self, target: int) -> bool:
cur = self.head
while cur:
while cur.nxt and cur.nxt.num < target:
cur = cur.nxt
if cur.nxt and cur.nxt.num == target:
return True
# move node to the next level
cur = cur.down
return False
def add(self, num: int) -> None:
# first find the prev nodes of position to insert
cur = self.head
prev = []
while cur:
while cur.nxt and cur.nxt.num < num:
cur = cur.nxt
prev.append(cur)
cur = cur.down
down_node, build_up = None, True
# insert from bottom up
while build_up and prev:
prev_node = prev.pop()
prev_node.nxt = Node(num, nxt=prev_node.nxt, down=down_node)
down_node = prev_node.nxt
build_up = random.randint(0,1) == 0
# if build_up is still True, we build another skiplist layer on top of
# current head layer to become the new head layer
if build_up:
self.head = Node(-1, nxt=None, down=self.head)
def erase(self, num: int) -> bool:
cur = self.head
found = False
while cur:
while cur.nxt and cur.nxt.num < num:
cur = cur.nxt
# if the next one is num, remove it from this layer
# then go down continue removing
if cur.nxt and cur.nxt.num == num:
cur.nxt = cur.nxt.nxt
found = True
cur = cur.down
return found
def debug(self):
# debug function to print out everything
cur1 = self.head
while cur1:
cur = cur1
s = str(cur.num)
while cur.nxt:
cur = cur.nxt
s += ' ' + str(cur.num)
cur1 = cur1.down
print(s)
# 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)复杂度平均时间复杂度: add, search, erase 因为 skiplist 的性质, 平均时间复杂度为 O(logn) 平均空间复杂度: O(n) skiplist 的空间复杂度,最后一层为 n, 上面一层为 n/2, ..., 1 为 O(n) 的平均空间复杂度 |
思路Redis 代码class Skiplist {
private static int DEFAULT_MAX_LEVEL= 32;
private static double DEFAULT_P_FACTOR = 0.25;
private Node head;
private int currentLevel;
class Node {
Integer value;
Node[] next;
public Node(Integer value, int size) {
this.value = value;
this.next = new Node[size];
}
@Override
public String toString() {
return String.valueOf(value);
}
}
private int randomLevel() {
int level = 1;
while (Math.random() < DEFAULT_P_FACTOR && level < DEFAULT_MAX_LEVEL) level++;
return level;
}
private Node findClosest(Node node, int levelIndex, int value) {
while ((node.next[levelIndex]) != null && value > node.next[levelIndex].value) {
node = node.next[levelIndex];
}
return node;
}
public Skiplist() {
head = new Node(null, DEFAULT_MAX_LEVEL);
currentLevel = 1;
}
public boolean search(int target) {
Node searchNode = head;
for (int i = currentLevel - 1; i >= 0; i--) {
searchNode = findClosest(searchNode, i, target);
if (searchNode.next[i] != null && searchNode.next[i].value == target) return true;
}
return false;
}
public void add(int num) {
int level = randomLevel();
Node updateNode = head;
Node newNode = new Node(num, level);
for (int i = currentLevel - 1; i >= 0; i--) {
updateNode = findClosest(updateNode, i, num);
if (i < level) {
// add last
if (updateNode.next[i] == null) updateNode.next[i] = newNode;
else {
// insert
Node temp = updateNode.next[i];
updateNode.next[i] = newNode;
newNode.next[i] = temp;
}
}
}
if (level > currentLevel) {
for (int i = currentLevel; i < level; i++) {
head.next[i] = newNode;
}
currentLevel = level;
}
}
public boolean erase(int num) {
boolean flag = false;
Node searchNode = head;
for (int i = currentLevel - 1; i >= 0; i--) {
searchNode = findClosest(searchNode, i, num);
if (searchNode.next[i] != null && searchNode.next[i].value == num) {
searchNode.next[i] = searchNode.next[i].next[i];
flag = true;
}
}
return flag;
}
}
/**
* 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);
*/ |
思路跳表 代码// 维护一个next指针和down指针
function Node(val, next = null, down = null) {
this.val = val;
this.next = next;
this.down = down;
}
var Skiplist = function () {
this.head = new Node(null);
};
/**
* @param {number} target
* @return {boolean}
*/
Skiplist.prototype.search = function (target) {
let head = this.head;
while (head) {
// 链表有序，从前往后走
while (head.next && head.next.val < target) {
head = head.next;
}
if (!head.next || head.next.val > target) {
// 向下走
head = head.down;
} else {
return true;
}
}
return false;
};
/**
* @param {number} num
* @return {void}
*/
Skiplist.prototype.add = function (num) {
const stack = [];
let cur = this.head;
// 用一个栈记录每一层可能会插入的位置
while (cur) {
while (cur.next && cur.next.val < num) {
cur = cur.next;
}
stack.push(cur);
cur = cur.down;
}
// 用一个标志位记录是否要插入，最底下一层一定需要插入(对应栈顶元素)
let isNeedInsert = true;
let downNode = null;
while (isNeedInsert && stack.length) {
let pre = stack.pop();
// 插入元素，维护 next/down 指针
pre.next = new Node(num, pre.next, downNode);
downNode = pre.next;
// 抛硬币确定下一个元素是否需要被添加
isNeedInsert = Math.random() < 0.5;
}
// 如果人品好，当前所有层都插入了改元素，还需要继续往上插入，则新建一层，表现为新建一层元素
if (isNeedInsert) {
this.head = new Node(null, new Node(num, null, downNode), this.head);
}
};
/**
* @param {number} num
* @return {boolean}
*/
Skiplist.prototype.erase = function (num) {
let head = this.head;
let seen = false;
while (head) {
// 在当前层往前走
while (head.next && head.next.val < num) {
head = head.next;
}
// 往下走
if (!head.next || head.next.val > num) {
head = head.down;
} else {
// 找到了该元素
seen = true;
// 从当前链表删除
head.next = head.next.next;
// 往下
head = head.down;
}
}
return seen;
}; |
代码class Skiplist {
private Node head;
public Skiplist() {
Node[] left = new Node[16];
Node[] right = new Node[16];
for(int i = 0; i < 16; i++) {
left[i] = new Node(-1);
right[i] = new Node(20001);
}
for(int i = 0; i < 15; i++) {
left[i].right = right[i];
left[i].down = left[i + 1];
right[i].down = right[i + 1];
}
left[15].right = right[15];
head = left[0];
}
public boolean search(int target) {
Node cur = head;
while(cur != null) {
if(cur.right.val > target) {
cur = cur.down;
} else if(cur.right.val < target) {
cur = cur.right;
} else {
return true;
}
}
return false;
}
public void add(int num) {
Node cur = head;
Deque<Node> stack = new LinkedList<>();
while(cur != null) {
if(cur.right.val >= num) {
stack.push(cur);
cur = cur.down;
} else {
cur = cur.right;
}
}
Node pre = null;
while(!stack.isEmpty()) {
cur = stack.pop();
Node node = new Node(num);
node.right = cur.right;
cur.right = node;
if(pre != null) node.down = pre;
pre = node;
if(Math.random() < 0.5) break;
}
}
public boolean erase(int num) {
Node cur = head;
boolean isRemoved = false;
while(cur != null) {
if(cur.right.val >= num) {
if(cur.right.val == num) {
isRemoved = true;
cur.right = cur.right.right;
}
cur = cur.down;
} else {
cur = cur.right;
}
}
return isRemoved;
}
}
class Node {
int val;
Node right;
Node down;
public Node(int val) {
this.val = val;
}
}复杂度分析时间复杂度O(logn) 空间复杂度O(n) |
class Skiplist {
ListNode head;
Random random = new Random();
public Skiplist() {
head = new ListNode(-1, null, null);
}
public boolean search(int target) {
ListNode p = head;
while (p != null) {
while (p.right != null && p.right.val < target) {
p = p.right;
}
if (p.right != null && p.right.val == target) {
return true;
}
p = p.down;
}
return false;
}
public void add(int num) {
ListNode p = head;
Deque<ListNode> stack = new ArrayDeque();
while (p != null) {
while (p.right != null && p.right.val < num) {
p = p.right;
}
stack.push(p);
p = p.down;
}
boolean insert = true;
ListNode down = null;
while (insert && !stack.isEmpty()) {
p = stack.pop();
p.right = new ListNode(num, p.right, down);
insert = insert && random.nextInt(2) == 0;
down = p.right;
}
if (insert) {
this.head = new ListNode(-1, null, head);
}
}
public boolean erase(int num) {
ListNode p = head;
boolean found = false;
while (p != null) {
while (p.right != null && p.right.val < num) {
p = p.right;
}
if (p.right != null && p.right.val == num) {
p.right = p.right.right;
found = true;
}
p = p.down;
}
return found;
}
private static class ListNode {
int val;
ListNode right;
ListNode down;
public ListNode(int val, ListNode right, ListNode down) {
this.val = val;
this.right = right;
this.down = down;
}
}
}
/**
* 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);
*/ |
思路
代码
Go Code: const (
MaxLevel = 32
Probability = 0.25
)
func randLevel() (level int) {
rand.Seed(time.Now().UnixNano())
for level = 1; rand.Float32() < Probability && level < MaxLevel; level++ {
}
return
}
type node struct {
key int
next []*node
}
type Skiplist struct {
head *node
level int
}
func Constructor() Skiplist {
return Skiplist{&node{0, make([]*node, MaxLevel)}, 1}
}
func (this *Skiplist) Search(target int) bool {
cur := this.head
for i := this.level-1; i > -1; i-- {
for cur.next[i] != nil {
if cur.next[i].key == target {
return true
} else if cur.next[i].key > target {
break
} else {
cur = cur.next[i]
}
}
}
return false
}
func (this *Skiplist) Add(num int) {
current := this.head
update := make([]*node, MaxLevel) // 新节点插入以后的前驱节点
for i := this.level - 1; i >= 0; i-- {
if current.next[i] == nil || current.next[i].key > num {
update[i] = current
} else {
for current.next[i] != nil && current.next[i].key < num {
current = current.next[i] // 指针往前推进
}
update[i] = current
}
}
level := randLevel()
if level > this.level {
// 新节点层数大于跳表当前层数时候, 现有层数 + 1 的 head 指向新节点
for i := this.level; i < level; i++ {
update[i] = this.head
}
this.level = level
}
node := &node{num, make([]*node, level)}
for i := 0; i < level; i++ {
node.next[i] = update[i].next[i]
update[i].next[i] = node
}
}
func (this *Skiplist) Erase(num int) bool {
flag := false
cur := this.head
for i := this.level-1; i > -1; i-- {
for cur.next[i] != nil {
if cur.next[i].key == num {
cur.next[i], cur.next[i].next[i] = cur.next[i].next[i], nil
flag = true
break
} else if cur.next[i].key > num {
break
} else {
cur = cur.next[i]
}
}
}
return flag
}复杂度分析 令 n 为数组长度。
|
代码class Skiplist:
def __init__(self):
self.head = Node(None)
def search(self, target: int) -> bool:
current=self.head
while current:
while current.next and current.next.value < target:
current=current.next
if current.next is None or current.next.value > target:
current=current.down
else:
return True
return False
def add(self, num: int) -> None:
stack=[]
current=self.head
while current:
while current.next and current.next.value < num:
current=current.next
stack.append(current)
current=current.down
fliped_needed=True
prev=None
while fliped_needed and stack:
current=stack.pop()
new_node=Node(num)
new_node.next=current.next
new_node.down = prev
prev = new_node
current.next=new_node
if random.random() < 0.5:
fliped_needed=False
if fliped_needed and len(stack)==0:
new_head=Node(None)
new_head.down = self.head
self.head = new_head
def erase(self, num: int) -> bool:
current=self.head
seen=False
while current:
while current.next and current.next.value < num:
current=current.next
if current.next is None or current.next.value > num:
current=current.down
else:
seen= True
current.next = current.next.next
current= current.down
return seen
class Node:
def __init__(self,value):
self.down=None
self.next=None
self.value=value复杂度Time: O(logn) Space: O(n) |
解题思路参考官方题解。先建节点类，在链表的节点的基础上增加一个down指针。每个节点可以向后，也可以向下走。初始化跳表的时候建立dummy head，便于以后插入新节点。删和查的方法类似，都是先向后走直到后一个节点值比目标值大的为止，之后转向向下走到下一层，然后继续向后走，继续往下走直到不能继续往下为止。增操作借助栈把每一层可以插入的位置记录下来，然后从最底层开始逐层向上插入。最底层保存所有节点，一定要插入，上面的各层随机投硬币决定是否插入新节点。如果我们要在最上面新增一层，那么需要建立新的dummy head，将跳表的head更新为新的dummy head即可。 代码class Skiplist {
class Node {
int val;
Node next;
Node down;
public Node(int val, Node next, Node down) {
this.val = val;
this.next = next;
this.down = down;
}
}
Node head;
public Skiplist() {
// create a dummy head
head = new Node(-1, null, null);
}
public boolean search(int target) {
Node cur = head;
while (cur != null) {
// move forward
while (cur.next != null && cur.next.val < target) {
cur = cur.next;
}
// move downward
if (cur.next != null && cur.next.val == target) {
return true;
}
cur = cur.down;
}
return false;
}
public void add(int num) {
Deque<Node> stack = new ArrayDeque<>();
Node cur = head;
// use stack to store the position to insert at each level
while (cur != null) {
while (cur.next != null && cur.next.val < num) {
cur = cur.next;
}
stack.push(cur);
cur = cur.down;
}
// use a variable to record whether we will need to insert, the bottom level must need insert
boolean needInsert = true;
Node downNode = null;
// build the Skiplist from bottom up
while (needInsert && stack.size() > 0) {
Node pre = stack.pop();
// insert element
pre.next = new Node(num, pre.next, downNode);
// update downNode
downNode = pre.next;
// flip a coin to decide whether we need to insert at upper level
needInsert = Math.random() < 0.5;
}
// current head layer becomes the new head layer
if (needInsert) {
head = new Node(-1, null, head);
}
}
public boolean erase(int num) {
Node cur = head;
boolean seen = false;
while (cur != null) {
// move forward
while (cur.next != null && cur.next.val < num) {
cur = cur.next;
}
// move downward
if (cur.next != null && cur.next.val == num) {
// found the element
seen = true;
// remove current node
cur.next = cur.next.next;
}
cur = cur.down;
}
return seen;
}
}复杂度分析
|
思路
|
代码块class Node {
// node节点中value表示节点的值，next指向包含所有层数的下一节点的数组，类似于下一列
constructor(value = null, size = 0) {
this.value = value;
this.next = new Array(size).fill(null);
}
}
var Skiplist = function () {
/**
* defaultMaxLevel随机层数概率，也就是随机出的层数，
* 在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1
*/
this.defaultMaxLevel = 16;
this.defaultFactor = 0.25;
this.head = new Node(null, this.defaultMaxLevel);
this.curentLevel = 1; //表示当前nodes的实际层数，从1开始
};
/**
* @param {number} target
* @return {boolean}
*/
Skiplist.prototype.search = function (target) {
let searchNode = this.head;
for (let i = this.curentLevel - 1; i >= 0; i--) {
searchNode = this.findClosest(searchNode, i, target);
if (searchNode.next[i] != null && searchNode.next[i].value == target) {
return true;
}
}
return false;
};
/**
* @param {number} num
* @return {void}
*/
Skiplist.prototype.add = function (num) {
let level = this.randomLevel();
let updateNode = this.head;
let newNode = new Node(num, level);
// 找到当前num所在的层数，并从该层开始添加，从结构中的当前层数开始找也就是最高层数往下找
for (let i = this.curentLevel - 1; i >= 0; i--) {
// 找到该层中距离num最近的node,将update传入有点类似于斜向下找
updateNode = this.findClosest(updateNode, i, num);
//这一层是小于num本身的层数时，就可以进行插入了，不是就不行
if (i < level) {
// 为空好办，直接插入
if (updateNode.next[i] == null) {
updateNode.next[i] = newNode;
} else {
let temp = updateNode.next[i];
updateNode.next[i] = newNode;
newNode.next[i] = temp;
}
}
}
// 完成后，发现随机出的层数大于了最大层，还需要更新最大层，
// 并且让所有超过curentLevel的层的head 指向newNode
if (level > this.curentLevel) {
for (let i = this.curentLevel; i < level; i++) {
this.head.next[i] = newNode;
}
this.curentLevel = level;
}
};
/** 删除该节点
* @param {number} num
* @return {boolean}
*/
Skiplist.prototype.erase = function (num) {
let flag = false;
let searchNode = this.head;
for (let i = this.curentLevel - 1; i >= 0; i--) {
searchNode = this.findClosest(searchNode, i, num);
if (searchNode.next[i] != null && searchNode.next[i].value == num) {
// 删除就是链表的删除节点，next指向next.next
searchNode.next[i] = searchNode.next[i].next[i];
flag = true;
}
}
return flag;
};
// 补充函数1：返回一个随即层数,控制在第一层的概率在3/4
Skiplist.prototype.randomLevel = function () {
let level = 1;
while (Math.random() < this.defaultFactor && level < this.defaultMaxLevel) {
level++;
}
return level;
};
// 补充函数2:顺着当前层开始查找，找出第一个 node.next大于target的节点或者空节点也可以
// 由于是node.next大于该节点，那么就是node小于它，node.next大于它，正好可以插在node后面
Skiplist.prototype.findClosest = function (node, levelIndex, target) {
while (
node.next[levelIndex] != null &&
node.next[levelIndex].value < target
) {
node = node.next[levelIndex];
}
return node;
}; |
|
title: "Day 91 1206. 设计跳表" 1206. 设计跳表题目不使用任何库函数，设计一个跳表。
跳表是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。
例如，一个跳表包含 [30, 40, 50, 60, 70, 90]，然后增加 80、45 到跳表中，以下图的方式操作：
Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons
跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。
在本题中，你的设计应该要包含这些函数：
bool search(int target) : 返回target是否存在于跳表中。
void add(int num): 插入一个元素到跳表。
bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。
了解更多 : https://en.wikipedia.org/wiki/Skip_list
注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。
样例:
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0); // 返回 false
skiplist.add(4);
skiplist.search(1); // 返回 true
skiplist.erase(0); // 返回 false，0 不在跳表中
skiplist.erase(1); // 返回 true
skiplist.search(1); // 返回 false，1 已被擦除
约束条件:
0 <= num, target <= 20000
最多调用 50000 次 search, add, 以及 erase操作。题目思路
struct Node
{
int key;
vector<Node*> nexts;
Node(int level,int k) : nexts(level + 1),key(k) {};
};
class Skiplist {
private:
Node* head;
int allLevel = -1;
public:
Skiplist() {
head = new Node(31,-1);
}
bool search(int key) {
Node* cur = head;
for(int curLevel = allLevel; curLevel >= 0; curLevel--)
{
while(cur -> nexts[curLevel] && cur -> nexts[curLevel] -> key < key) {
cur = cur -> nexts[curLevel];
}
if(cur -> nexts[curLevel] && cur -> nexts[curLevel] -> key == key)
return true;
}
return false;
}
void add(int key) {
int newLevel = getLevel();
allLevel = max(allLevel, newLevel);
Node* cur = head;
Node* newNode = new Node(newLevel, key);
for(int curLevel = allLevel; curLevel >= 0; curLevel--)
{
while(cur -> nexts[curLevel] && cur -> nexts[curLevel] -> key < key){
cur = cur -> nexts[curLevel];
}
if(curLevel <= newLevel)
{
newNode -> nexts[curLevel] = cur -> nexts[curLevel];
cur -> nexts[curLevel] = newNode;
}
}
}
bool erase(int key) {
Node* cur = head;
bool flag = false;
for(int curLevel = allLevel; curLevel >= 0; curLevel--)
{
while(cur -> nexts[curLevel] && cur -> nexts[curLevel] -> key < key) {
cur = cur -> nexts[curLevel];
}
if(cur -> nexts[curLevel] && cur -> nexts[curLevel] -> key == key) {
flag = true;
Node* tmp = cur -> nexts[curLevel] -> nexts[curLevel];
cur -> nexts[curLevel] -> nexts[curLevel] = nullptr;
cur -> nexts[curLevel] = tmp;
}
}
if(flag == false) return false;
return true;
}
int getLevel() {
int ans = 0;
while(ans < 32 && rand() < RAND_MAX * 0.25) ans++;
return ans;
}
};
/**
* 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);
*/复杂度
|
思路链表。 代码(C++)struct Node
{
Node* right;
Node* down;
int val;
Node(Node *right, Node *down, int val)
: right(right), down(down), val(val){}
};
class Skiplist {
private:
Node *head;
// 预先分配后能到 104ms （94%）
const static int MAX_LEVEL = 32;
// 查找时临时使用的变量
vector<Node*> pathList;
public:
Skiplist() {
head = new Node(NULL, NULL, -1); //初始化头结点
pathList.reserve(MAX_LEVEL);
}
bool search(int target)
{
Node *p = head;
while(p)
{
// 左右寻找目标区间
while(p->right && p->right->val < target)
{
p = p->right;
}
// 没找到目标值，则继续往下走
if(!p->right || target < p->right->val)
{
p = p->down;
}
else
{
//找到目标值，结束
return true;
}
}
return false;
}
void add(int num) {
// cout << "add " << num << endl;
//从上至下记录搜索路径
pathList.clear();
Node *p = head;
// 从上到下去搜索 次小于num的 数字，等于就是另外一种实现里的 prevs
while(p)
{
// 向右找到次小于num的p
while (p->right && p->right->val < num)
{
p = p->right;
}
pathList.push_back(p);
p = p->down;
}
bool insertUp = true;
Node* downNode = NULL;
// 从下至上搜索路径回溯，50%概率
// 这里实现是会保证不会超过当前的层数的，然后靠头结点去额外加层， 即每次新增一层
while (insertUp && pathList.size() > 0)
{
Node *insert = pathList.back();
pathList.pop_back();
// add新结点
insert->right = new Node(insert->right,downNode,num);
// 把新结点赋值为downNode
downNode = insert->right;
// 50%概率
insertUp = (rand()&1)==0;
// cout << " while new node " << num << " insertUp " << insertUp << endl;
}
// 插入新的头结点，加层
if(insertUp)
{
// cout << " insertUp new node " << num << endl;
head = new Node(new Node(NULL,downNode,num), head, -1);
}
}
bool erase(int num) {
Node *p = head;
bool seen = false;
while (p)
{
// 当前层向右找到次小的点
while (p->right && p->right->val < num)
{
p = p->right;
}
// 无效点，或者 太大， 则到下一层去
if (!p->right || p->right->val > num)
{
p = p->down;
}
else
{
// 搜索到目标结点，进行删除操作，结果记录为true
// 继续往下层搜索，删除一组目标结点
seen = true;
p->right = p->right->right;
p = p->down;
}
}
return seen;
}
};复杂度分析
|
|
class Skiplist { |
class Skiplist {
class Node{
Node next;
Node down;
int val;
Node(){};
Node(int val , Node next , Node down){
this.val = val;
this.next = next;
this.down = down;
};
}
Node root;
public Skiplist() {
root = new Node();
}
public boolean search(int target) {
Node head = this.root;
while(head != null){
while(head.next !=null && head.next.val < target){
head = head.next;
}
if(head.next == null || head.next.val > target){
head = head.down;
}
else{
return true;
}
}
return false;
}
public void add(int num) {
LinkedList<Node> stack = new LinkedList<>();
Node cur = this.root;
while(cur != null){
while(cur.next != null && cur.next.val < num){
cur = cur.next;
}
stack.push(cur);
cur = cur.down;
}
boolean isneedinsert = true;
Node downnode = null;
while(isneedinsert && stack.size() != 0){
Node x = stack.pop();
x.next = new Node(num , x.next,downnode);
downnode = x.next;
double rand =Math.random() ;
isneedinsert = rand <0.5 ? true : false;
}
if(isneedinsert){
this.root = new Node(-1, new Node(num, null, downnode), this.root);
}
}
public boolean erase(int num) {
Node head = this.root;
boolean seen = false;
while(head!=null){
while(head.next !=null && head.next.val < num){
head = head.next;
}
if(head.next == null || head.next.val > num ){
head = head.down;
}else{
seen = true;
head.next = head.next.next;
head = head.down;
}
}
return seen;
}
}
/**
* 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);
*/ |
|
class Solution: |
思路:需要实现以下 3 个函数: bool search(int target) : 返回target是否存在于跳表中。 代码:实现语言: C++ struct Node {
Node *right, *down;
int val;
Node(Node* right, Node* down, int val): right(right), down(down), val(val) {}
};
class Skiplist {
Node* head;
vector<Node*> insertPoints;
public:
Skiplist() {
head = new Node(nullptr, nullptr, 0);
}
bool search(int target) {
Node* p = head;
while (p)
{
while (p->right && p->right->val < target) /* 找当前层的1个适合的区间: 如果p->right变成NULL或target <= p->right结点的值时说明找到合适位置了, 否则继续右移 */
p = p->right;
if (!p->right || p->right->val > target) // 没找到, 就继续到下1层去找
p = p->down;
else
return true;
}
return false;
}
void add(int num)
{
insertPoints.clear();
Node* p = head;
while (p)
{
while (p->right && p->right->val < num)
p = p->right;
insertPoints.push_back(p);
p = p->down;
}
Node* downNode = nullptr;
bool insertUp = true;
while (insertUp && insertPoints.size())
{
Node* ins = insertPoints.back();
insertPoints.pop_back();
ins->right = new Node(ins->right, downNode, num);
downNode = ins->right;
insertUp = (rand() & 1) == 0; // 50% 的可能性
}
if (insertUp) // 创建一个新的layer
{
head = new Node(new Node(nullptr, downNode, num), head, 0);
}
}
bool erase(int num)
{
Node* p = head;
bool seen = false; // 跳表中是否存在要删的值
while (p)
{
while (p->right && p->right->val < num)
p = p->right;
if (!p->right || p->right->val > num) // 没找到要删的值, 就继续到下1层去找
p = p->down;
else /* 找到了要删的值, 就删除这个结点 */
{
seen = true;
p->right = p->right->right;
p = p->down;
}
}
return seen;
}
}; |
代码class Skiplist {
/* 最大层数
*/
private static int DEFAULT_MAX_LEVEL = 32;
/**
* 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1
*/
private static double DEFAULT_P_FACTOR = 0.25;
Node head = new Node(null,DEFAULT_MAX_LEVEL); //头节点
int currentLevel = 1; //表示当前nodes的实际层数，它从1开始
public Skiplist() {
}
public boolean search(int target) {
Node searchNode = head;
for (int i = currentLevel-1; i >=0; i--) {
searchNode = findClosest(searchNode, i, target);
if (searchNode.next[i]!=null && searchNode.next[i].value == target){
return true;
}
}
return false;
}
public void add(int num) {
int level = randomLevel();
Node updateNode = head;
Node newNode = new Node(num,level);
// 计算出当前num 索引的实际层数，从该层开始添加索引
for (int i = currentLevel-1; i>=0; i--) {
//找到本层最近离num最近的list
updateNode = findClosest(updateNode,i,num);
if (i<level){
if (updateNode.next[i]==null){
updateNode.next[i] = newNode;
}else{
Node temp = updateNode.next[i];
updateNode.next[i] = newNode;
newNode.next[i] = temp;
}
}
}
if (level > currentLevel){ //如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode
for (int i = currentLevel; i < level; i++) {
head.next[i] = newNode;
}
currentLevel = level;
}
}
public boolean erase(int num) {
boolean flag = false;
Node searchNode = head;
for (int i = currentLevel-1; i >=0; i--) {
searchNode = findClosest(searchNode, i, num);
if (searchNode.next[i]!=null && searchNode.next[i].value == num){
//找到该层中该节点
searchNode.next[i] = searchNode.next[i].next[i];
flag = true;
continue;
}
}
return flag;
}
private Node findClosest(Node node,int levelIndex,int value){
while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
node = node.next[levelIndex];
}
return node;
}
private static int randomLevel(){
int level = 1;
while (Math.random()<DEFAULT_P_FACTOR && level<DEFAULT_MAX_LEVEL){
level ++ ;
}
return level;
}
class Node{
Integer value;
Node[] next;
public Node(Integer value,int size) {
this.value = value;
this.next = new Node[size];
}
@Override
public String toString() {
return String.valueOf(value);
}
}
} |
|
class Skiplist_st { } |
type Node struct {
val int
Right, Down *Node
}
func NewNode(v int, r, d *Node) *Node {
return &Node{val: v, Right: r, Down: d}
}
type Skiplist struct {
level int
Head *Node
}
func Constructor() Skiplist {
return Skiplist{level: 1, Head: NewNode(0,nil,nil) }
}
func (this *Skiplist) Search(target int) bool {
// 申请临时变量指向头部
cur := this.Head
// 直接while到死
for cur != nil {
// 如果cur的右边不为空，并且右边的值小于target...
for cur.Right != nil && cur.Right.val < target {
// ... 向右边移动
cur = cur.Right
} // 此时已经到了最右边（边界，或者小于右边的值了，准备向下走）
// 如果右边的值还等于目标值..
if cur.Right != nil && cur.Right.val == target {
// ...直接返回
return true
}
// 否则向下走
cur = cur.Down
}
return false
}
func (this *Skiplist) Add(num int) {
rLevel := 1
// 如果小于等于总的层数，就掷***，rand.Int31()%2会得到一个1或者0的数，如果是0就给这个值的所在层总数加1
for rLevel <= this.level && ((rand.Int31() & 1) == 0) {
rLevel++ // 本值的越大概率越小
}
// 如果总层数已经超过了最大层数...
if rLevel > this.level {
// ...反向赋值，增长最大层数
this.level = rLevel
// 头结点换成新的，值就是插入值，右边是nil，下面是原来的头
this.Head = NewNode(num, nil, this.Head)
}
cur := this.Head
var last *Node = nil
// 从最大层开始递减到第一层
for l := this.level; l >= 1; l-- {
// cur的右不为nil，并且右方的值小于要插入的值...(找到一个合适的区间)
for cur.Right != nil && cur.Right.val < num {
// ... 向右走
cur = cur.Right
}
// 如果l小于rLevel，也就是本层依然需要这个节点..
if l <= rLevel { // 在这个语句前已经找到了最大的节点，要么右边为空，要么右边比本值大。
// ... 创建新的节点，值是要插入的值，右边就是原来的右边，下面为空
cur.Right = NewNode(num, cur.Right, nil)
// last是之前添加的点，具体在下方 last = cur.Right
// 如果last存在，就应该把last（上层的cur.right）的下，指向当前新插入的节点
if last != nil {
// last的下就是cur的右
last.Down = cur.Right
}
// last是要等于cur的右边的
last = cur.Right
}
cur = cur.Down
}
}
func (this *Skiplist) Erase(num int) bool {
cur := this.Head
var seen = false
for l := this.level; l >= 1; l-- {
for cur.Right != nil && cur.Right.val < num {
cur = cur.Right
}
if cur.Right != nil && cur.Right.val == num {
seen = true
cur.Right = cur.Right.Right
}
cur = cur.Down
}
return seen
}
/**
* 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);
*/ |
struct Node{
//节点值
int val;
//向右和向左指针
Node *right, *down;
Node(int val, Node *right, Node *down) :val(val), right(right), down(down){}
};
class Skiplist {
private:
int HEAD_VALUE = -1;
Node *HEAD = new Node(HEAD_VALUE, nullptr, nullptr);
Node *head;//左上角头节点
int levels;//当前层级，即head节点所在的最高层数
int length;//跳表长度，即原链表的节点个数
public:
Skiplist() {
head = HEAD;
levels = 1;
length = 1;
}
/*
* head开始，从左往右，从上往下查找
* 1.若节点值小于目标值，则往右查找
* 2.节点值等于目标值，则返回true
* 3.节点值大于目标值,则向下一层级查找
*/
bool search(int target){
Node *node = head;
while (node != nullptr){
//1.在同一层级上，从左往右查找知道链表的结尾
while (node->right != nullptr && node->right->val < target){
node = node->right;
}
//2.若找到符合条件的节点,即该节点的值与target相等,则返回true
if (node->right != nullptr && node->right->val == target){
return true;
}
//3.若node.right的值大于目标target,则向下一层
node = node->down;
}
//若在最后一层也未找到符合条件的节点，则返回false
return false;
}
/*
* 逐层遍历，并删除每一层符合条件的节点
* 1.获取指定数据节点的前一个节点
* 2.将指定节点与当前层链表断开
* 3.下移，重复1 2操作
*/
bool erase(int num){
Node *node = head;
bool exist = false;
while (node != nullptr){
//1.获取指定数据节点的前一个节点
while (node->right != nullptr && node->right->val < num){
node = node->right;
}
//2.若该节点为目标节点，则将其与当前层链表断开
Node *right = node->right;//需要断开的节点
if (right != nullptr && right->val == num){
//断开操作
node->right = right->right;
right->right = nullptr;
exist = true;
}
//3.下移，重复之前操作
node = node->down;
}
return exist;
}
/*
* 将节点插入到原链表中正确的排序位置
* 1.定位插入位置;在原链表中>=num的最小节点前
* 2.插入节点
* 3.根据抛硬币决定是否建立索引
*/
void add(int num){
Node *node = head;
//使用数组记录，每一层可能生成索引位置的节点
vector<Node*> nodes(levels);
int i = 0;
//1.定位插入位置;在原链表中>=num的最小节点前
while (node != nullptr){
while (node->right != nullptr && node->right->val < num){
node = node->right;
}
//右侧可能为null，或大于目标数值，或等于目标数值
nodes[i++] = node;
//继续查找下一层的位置
node = node->down;
}
//2.插入新节点
//取出nodes中的最后一个元素。即原链表中<num的最大的一个节点
node = nodes[--i];
//进行插入操作
Node *newNode = new Node(num, node->right, nullptr);
node->right = newNode;
++length;//原链表的长度加一
//3.根据抛硬币决定是否建立索引
addIndicesByCoinFlip(newNode, nodes, i);//i的值代表索引层数，不包括原链表
}
/**
* 抛硬币决定是否给新节点建立索引
* 索引层级可能超过现有跳表的层数，再抛一次硬币决定是否生成更高的索引
* 1.抛硬币，决定是否给在现有跳表层级建立索引
* 2.抛硬币，决定是否建立超过跳表层数的索引层
*/
private:
void addIndicesByCoinFlip(Node *target, vector<Node*> &nodes, int indices){
Node *downNode = target;
int coins = (rand() & 1) == 0;
while (coins == 1 && levels < (length >> 6)){
if (indices > 0){
Node *prev = nodes[--indices];//首先时数组中的倒数第二个元素
//建立索引
Node *newNode = new Node(target->val, prev->right, downNode);
prev->right = newNode;
//更新downNode
downNode = newNode;
coins = (rand() & 1) == 0;
}
else {//新建一个索引层级
//新建索引节点和head节点
Node *newNode = new Node(target->val, nullptr, downNode);
Node *newhead = new Node(HEAD_VALUE, newNode, head);
head = newhead;//head指针上移
++levels;//跳表层数加一
}
}
}
};又是一个没接触过的东东 |
【Day 91】1206. 设计跳表代码class Skiplist {
public:
Skiplist() : head(new Node()), maxLevels(0), length(0) {}
void add(int num) {
Node* temp = head;
// 记录每一层可能生成索引位置的节点
vector<Node*> nodes;
// 1.定位插入位置;在原链表中 <=num 的最大节点前
while (temp) {
while (temp->right && temp->right->val < num) temp = temp->right;
nodes.emplace_back(temp);
temp = temp->down;
}
// 要不要在当前层建索引
bool insertIndex = true;
// 保存上一次建立的索引，本次建索引时将 down 指针连接到这里
Node* downNode = nullptr;
// 插入数据节点到最低层的链表（并且从下往上建立索引）
while(insertIndex && !nodes.empty()) {
temp = nodes.back(); nodes.pop_back();
temp->right = new Node(num, downNode, temp->right);
downNode = temp->right; // 保存当前节点让上一层索引的 down 指针连接
insertIndex = ((rand() & 1) == 0); // 是否还要再往上层建索引
}
// 根据概率新建一层索引
if(insertIndex) {
temp = new Node(num, downNode, nullptr);
head = new Node(-1, head, temp);
++maxLevels;
}
++length; // 更新节点数量
}
bool search(int target) {
Node* temp = head;
while(temp) {
// 1.在同一层级上，从左往右查找直到链表的结尾
while (temp->right && temp->right->val < target) temp = temp->right;
// 2.若找到符合条件的节点，即该节点的值与 target 相等,则返回true
if(temp->right && temp->right->val == target) return true;
// 3.若 node->right->val 大于(即不等于) target，则向下一层
temp = temp->down;
}
return false;
}
bool erase(int num) {
Node* temp = head;
bool exist = false;
while (temp) {
while (temp->right && temp->right->val < num) temp = temp->right;
Node* right = temp->right;
Node* last = temp;
// 从上往下逐个删除
if(right && right->val == num){
exist = true;
last = temp;
temp->right = right->right;
right->right = nullptr;
delete right;
}
temp = temp->down;
// 是否需要删除这一层（最上层）索引
if(last == head && last->right == nullptr) {
Node* headShouldDelete = head;
head = head->down;
delete headShouldDelete;
--maxLevels;
}
}
if(exist) --length; // 更新节点数量
return exist;
}
private:
struct Node {
int val;
Node* down;
Node* right;
Node(int _val = -1, Node* _down = nullptr, Node* _right = nullptr) : val(_val), down(_down), right(_right) {}
};
Node* head;
int maxLevels; // 索引层数
int length; // 记录节点数量
};
/**
* 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);
*/ |
class Skiplist {
static class Node {
public static int DEFAULT_MAX_LEVEL = 32;
public static double DEFAULT_P_FACTOR = 0.25;
int value;
Node[] next;
public Node(int value, int size) {
this.value = value;
next = new Node[size];
}
public Node(int value) {
this(value, randomLevel());
}
private static int randomLevel() {
int level = 1;
while (Math.random() < DEFAULT_P_FACTOR && level < DEFAULT_MAX_LEVEL) {
level++;
}
return level;
}
}
private Node head;
private int currentLevel;
public Skiplist() {
head = new Node(-1, Node.DEFAULT_MAX_LEVEL);
currentLevel = 1;
}
public boolean search(int target) {
Node node = head;
for (int i = currentLevel - 1; i >= 0; i--) {
node = findClosest(node, i, target);
if (node.next[i] != null && node.next[i].value == target) {
return true;
}
}
return false;
}
public void add(int num) {
Node updateNode = head;
Node newNode = new Node(num);
int level = newNode.next.length;
for (int i = currentLevel - 1; i >= 0; i--) {
updateNode = findClosest(updateNode, i, num);
if (i < level) {
newNode.next[i] = updateNode.next[i];
updateNode.next[i] = newNode;
}
}
if (level > currentLevel) {
for (int i = currentLevel; i < level; i++) {
head.next[i] = newNode;
}
currentLevel = level;
}
}
public boolean erase(int num) {
boolean flag = false;
Node node = head;
for (int i = currentLevel - 1; i >= 0; i--) {
node = findClosest(node, i, num);
if (node.next[i] != null && node.next[i].value == num) {
flag = true;
node.next[i] = node.next[i].next[i];
}
}
return flag;
}
private Node findClosest(Node node, int level, int target) {
while (node.next[level] != null && node.next[level].value < target) {
node = node.next[level];
}
return node;
}
} |
|
python |
思路参考solution 代码`function Node(val, next = null, down = null) { var Skiplist = function () { /**
/**
// 用一个标志位记录是否要插入，最底下一层一定需要插入(对应栈顶元素) // 如果人品好，当前所有层都插入了改元素，还需要继续往上插入，则新建一层，表现为新建一层元素 /**
|
代码
C++ Code: struct Node
{
Node* right;
Node* down;
int val;
Node(Node *right, Node *down, int val)
: right(right), down(down), val(val){}
};
class Skiplist {
private:
Node *head;
const static int MAX_LEVEL = 32;
vector<Node*> pathList;
public:
Skiplist() {
head = new Node(NULL, NULL, -1);
pathList.reserve(MAX_LEVEL);
}
bool search(int target)
{
Node *p = head;
while(p)
{
while(p->right && p->right->val < target)
{
p = p->right;
}
if(!p->right || target < p->right->val)
{
p = p->down;
}
else
{
return true;
}
}
return false;
}
void add(int num) {
pathList.clear();
Node *p = head;
while(p)
{
while (p->right && p->right->val < num)
{
p = p->right;
}
pathList.push_back(p);
p = p->down;
}
bool insertUp = true;
Node* downNode = NULL;
while (insertUp && pathList.size() > 0)
{
Node *insert = pathList.back();
pathList.pop_back();
insert->right = new Node(insert->right,downNode,num);
downNode = insert->right;
insertUp = (rand()&1)==0;
}
if(insertUp)
{
head = new Node(new Node(NULL,downNode,num), head, -1);
}
}
bool erase(int num) {
Node *p = head;
bool seen = false;
while (p)
{
while (p->right && p->right->val < num)
{
p = p->right;
}
if (!p->right || p->right->val > num)
{
p = p->down;
}
else
{
seen = true;
p->right = p->right->right;
p = p->down;
}
}
return seen;
}
};
|
|
|
思路 实现语言: C++
struct Node {
Node *right, *down;
int val;
Node(Node* right, Node* down, int val): right(right), down(down), val(val) {}
};
class Skiplist {
Node* head;
vector<Node*> insertPoints;
public:
Skiplist() {
head = new Node(nullptr, nullptr, 0);
}
bool search(int target) {
Node* p = head;
while (p)
{
while (p->right && p->right->val < target)
p = p->right;
if (!p->right || p->right->val > target)
p = p->down;
else
return true;
}
return false;
}
void add(int num)
{
insertPoints.clear();
Node* p = head;
while (p)
{
while (p->right && p->right->val < num)
p = p->right;
insertPoints.push_back(p);
p = p->down;
}
Node* downNode = nullptr;
bool insertUp = true;
while (insertUp && insertPoints.size())
{
Node* ins = insertPoints.back();
insertPoints.pop_back();
ins->right = new Node(ins->right, downNode, num);
downNode = ins->right;
insertUp = (rand() & 1) == 0;
}
if (insertUp)
{
head = new Node(new Node(nullptr, downNode, num), head, 0);
}
}
bool erase(int num)
{
Node* p = head;
bool seen = false;
while (p)
{
while (p->right && p->right->val < num)
p = p->right;
if (!p->right || p->right->val > num)
p = p->down;
else
{
seen = true;
p->right = p->right->right;
p = p->down;
}
}
return seen;
}
};复杂度分析 |
复杂度分析 |
|
struct Node { class Skiplist { public: }; |
|
class Solution: |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and others
1206. 设计跳表
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/design-skiplist/
前置知识
暂无
题目描述
null
The text was updated successfully, but these errors were encountered: