| Category | Difficulty | Likes | Dislikes |
|---|
| algorithms | Hard (53.80%) | 14 | - |
Tags
Unknown
Companies
Unknown
不使用任何库函数，设计一个跳表。
跳表是在 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
注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。
样例:
1
2
3
4
5
6
7
8
9
10
11
| 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操作。
Discussion | Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| import math
import random
maxLevel = 16
power = 2
maxRand = power ** maxLevel - 1
randLevel = lambda: maxLevel - int(math.log(random.randint(1, maxRand), power))
class SkipNode:
def __init__(self, val, level = 1):
self.val = val #节点值
self.next = [None] * level #下一个节点指针数组
def level(self) -> int:
return len(self.next)
class Skiplist:
def __init__(self):
tail = SkipNode(float('inf'), maxLevel)
self.head = SkipNode(-float('inf'), maxLevel)
for i in range(maxLevel):
self.head.next[i] = tail
def search(self, target: int) -> bool:
#从顶部开始遍历各层链表，寻找目标点
node = self.head
for i in range(maxLevel-1, -1, -1):
#遍历i层的节点
while node:
#找到目标节点
if node.val == target:
return True
#如果当前节点值 < 目标值 且 下一个节点值 > 目标值
elif node.val < target and node.next[i].val > target:
# 如果为最底层节点，则未找到, 返回False
if i == 0:
return False
else:
#否则，中断本层遍历，继续下层遍历
break
#否则下一个结点值 < 目标值，遍历本层下一个节点
else:
node = node.next[i]
return False
def display(self):
node = self.head
while node:
print(str(node.val), len(node.next))
node = node.next[0]
def add(self, num: int) -> None:
#生成新节点，节点level 随机生成
newNodeLevel = randLevel()
newNode = SkipNode(num, newNodeLevel)
#从顶部开始遍历各层链表，寻找插入点，将新节点插入其中
node = self.head
for i in range(newNodeLevel-1, -1, -1):
#遍历i层的节点
while node:
#如果下一个结点值 >= 插入值，则插入本层结点
if node.next[i] and node.next[i].val >= num:
newNode.next[i] = node.next[i]
node.next[i] = newNode
#中断本层遍历，转入下一层
break
#下一个结点值 < 插入值
else:
#遍历本层下一个节点
node = node.next[i]
def erase(self, num: int) -> bool:
ans = False
node = self.head
for i in range(maxLevel-1, -1, -1):
while node:
#下一个结点值为为删除点
if node.next[i] and node.next[i].val == num:
ans = True
node.next[i] = node.next[i].next[i]
#继续处理下层结点
break
#当前节点值<目标值 且 下一个节点值>目标值
elif node.val < num and node.next[i].val > num:
#中断本层遍历，转入下一层
break
#当前节点和下一个节点值均 小于 目标值
else:
#遍历本层下一个节点
node = node.next[i]
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
| // @lc code=start
use std::cell::RefCell;
use std::rc::Rc;
use rand::Rng;
const P_FACTOR: f64 = 0.25;
const LEVEL_MAX: usize = 32;
// 跳表节点间的连接
type Link = Option<Rc<RefCell<SkipNode>>>;
// 跳表节点
struct SkipNode {
val: i32,
next: Vec<Link>,
}
impl SkipNode {
fn new(level: usize, val: i32) -> Self {
Self {
val,
next: vec![None; level]
}
}
}
// 跳表
struct Skiplist {
level: usize,
head: Link, //跳表头
}
// 生成随机level
fn random_level() -> usize {
let mut level = 1;
let mut rng = rand::thread_rng();
while level < LEVEL_MAX && rng.gen::<f64>() < P_FACTOR {
level += 1;
}
level
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl Skiplist {
fn new() -> Self {
Self {
level: LEVEL_MAX,
head: Some(Rc::new(RefCell::new(SkipNode::new(LEVEL_MAX, std::i32::MIN)))),
}
}
fn search(&self, target: i32) -> bool {
let mut link_opt = self.head.clone();
for level in (0..self.level).rev() {
while let Some(link) = link_opt.clone() {
if link.borrow().val == target {
return true;
} else if let Some(next) = link.borrow().next[level].clone()
.filter(|l| l.borrow().val <= target) {
link_opt.replace(next.clone());
} else {
break;
}
}
}
return false;
}
fn add(&self, num: i32) {
let level = random_level();
let new_node = Rc::new(RefCell::new(SkipNode::new(level, num)));
let mut link_opt = self.head.clone();
for l in (0..level).rev() {
while let Some(link) = link_opt.clone() {
let mut node = link.borrow_mut();
if let Some(next) = node.next[l].clone()
.filter(|n| n.borrow().val < num) {
link_opt.replace(next.clone());
} else {
if let Some(next) = node.next[l].clone()
.filter(|n| n.borrow().val >= num) {
new_node.borrow_mut().next[l] = node.next[l].take();
}
node.next[l].replace(new_node.clone());
break;
}
}
}
}
/// erase node which val == num
/// when node exist, remove node and return true
/// else return false
fn erase(&self, num: i32) -> bool {
let mut existed = false;
let mut link_opt = self.head.clone();
let mut level = self.level - 1;
for l in (0..self.level).rev() { //从上至下,依次遍历各层
while let Some(link) = link_opt.clone() {
let mut node = link.borrow_mut();
// 如果下个节点的值<=目标值
if let Some(next) = node.next[l].clone()
.filter(|n| n.borrow().val <= num) {
let next_val = next.borrow().val;
if next_val < num { //下个节点值<目标节点, 向右移动指针
link_opt.replace(next.clone());
} else if next_val == num { //下个节点值==需要删除的节点
node.next[l] = next.clone().borrow_mut().next[l].take(); //移除需要被删除的节点
existed = true; //存在需要被删除的节点
break;
} else {
break;
}
} else { //下个节点值>目标值或不存在下个节点
break; //退出当前层遍历,进入下一层遍历
}
}
}
existed
}
}
/**
* Your Skiplist object will be instantiated and called as such:
* let obj = Skiplist::new();
* let ret_1: bool = obj.search(target);
* obj.add(num);
* let ret_3: bool = obj.erase(num);
*/
// @lc code=end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
let mut sl = Skiplist::new();
sl.add(1);
sl.add(2);
sl.add(3);
assert!(sl.search(0) == false);
sl.add(4);
assert!(sl.search(1) == true);
assert!(sl.erase(0) == false);
assert!(sl.erase(1) == true);
assert!(sl.search(1) == false);
}
}
|