• 博客访问： 3260124
• 博文数量： 287
• 博客积分： 0
• 博客等级： 民兵
• 技术积分： 2109
• 用 户 组： 普通用户
• 注册时间： 2019-10-28 13:40

2022年（60）

2021年（155）

2020年（50）

2019年（22）

2021-03-23 17:21:01

Python实现

class Skiplist:

def __init__(self):

def search(self, target: int) -> bool:

while node:

while node.right and node.right.val < target:

node = node.right

if node.right and node.right.val == target:

return True

node = node.down  # 这一层没有，往下一层

return False

def add(self, num: int) -> None:

nodes = []

while node:

# Move to the right in the current level

while node.right and node.right.val < num:

node = node.right

nodes.append(node)

# Move to the next level

node = node.down

insert = True

down = None

while insert and nodes:

node = nodes.pop()

node.right = Node(num, node.right, down)

down = node.right

insert = (random.getrandbits(1) == 0)

# Create a new level with a dummy head

# right = None

if insert:

def erase(self, num: int) -> bool:

found = False

while node:

# Move to the right in the current level

while node.right and node.right.val < num:

node = node.right

# Find the target node

if node.right and node.right.val == num:

# Delete by skipping

node.right = node.right.right

found = True

# Move to the next level

node = node.down

return found

class Node:

def __init__(self, val=-1, right=None, down=None):

self.val = val

self.right = right

self.down = down

# Your Skiplist object will be instantiated and called as such:

# obj = Skiplist()

# param_1 = obj.search(target)

# param_3 = obj.erase(num)

Java实现

class Skiplist {

class Node {

int val;

Node right;

Node down;

Node(){

this(-1, null, null);

}

Node(int val, Node right, Node down) {

this.val = val;

this.right = right;

this.down = down;

}

}

public Skiplist() {

}

public boolean search(int target) {

while(node != null) {

while(node.right != null && node.right.val < target)

node = node.right;

if(node.right != null && node.right.val == target)

return true;

node = node.down;

}

return false;

}

while(node != null) {

while(node.right != null && node.right.val < num) {

node = node.right;

}

node = node.down;

}

// 向上回溯，根据概率判断是否新增节点

boolean isInsert = true;    // 最下面一层 100% 要新增

double c = 1.0;

Node down = null;           // 记录一下下面一层的down指针

while 货币符号(!nodes.isEmpty() && isInsert) {

Node cur = nodes.removeLast();

cur.right = new Node(num, cur.right, down);

down = cur.right;

isInsert = count(c++);

}

if(isInsert)

}

public boolean erase(int num) {

boolean res = false;

while(node != null) {

while(node.right != null && node.right.val < num) {

node = node.right;

}

if(node.right != null && node.right.val == num) {

res = true;

node.right = node.right.right;

}

node = node.down;

}

return res;

}

// 计算概率

static boolean count(double i) {

double x = new Random().nextDouble();

double y = 1 / Math.pow(2, i);

return x <= y;

}

}