[合集] 【参加活动】岁月是把杀猪刀。。。还是小鳅# pets - 心有所宠
w*z
1 楼
The program is pretty easy compared to M and F, just for reference
shows a collection of linked-lists.
The bottom-most linked-list contains all the elements sorted in ascending
order (ie: 5, 8, 25, 28, etc ...).
Each linked-list above it allows you to jump to specific nodes in the bottom
list.
Each linked-list is sparser and contains fewer nodes than the linked-list
below it.
If a linked-list has a node for a particular value, then all the other
linked-lists below it will also contain that node, allowing you to cross
from one linked-list to another at these nodes.
For example, at the node with value 8 you can cross from the top-most linked
-list to any of the other linked-lists below it.
Using this structure, how would you efficiently find a value, for example,
70?
class Node {
int value;
Node next;
Node below;
}
X ------> X -----------------------------------------> NULL
X ------> X ------> X ------> X ---------------------> NULL
X ------> X -> X -> X ------> X -----------> X ------> NULL
X -> X -> X -> X -> X -> X -> X -> X -> X -> X -> X -> NULL
H 5 8 25 28 33 52 55 70 81 83
shows a collection of linked-lists.
The bottom-most linked-list contains all the elements sorted in ascending
order (ie: 5, 8, 25, 28, etc ...).
Each linked-list above it allows you to jump to specific nodes in the bottom
list.
Each linked-list is sparser and contains fewer nodes than the linked-list
below it.
If a linked-list has a node for a particular value, then all the other
linked-lists below it will also contain that node, allowing you to cross
from one linked-list to another at these nodes.
For example, at the node with value 8 you can cross from the top-most linked
-list to any of the other linked-lists below it.
Using this structure, how would you efficiently find a value, for example,
70?
class Node {
int value;
Node next;
Node below;
}
X ------> X -----------------------------------------> NULL
X ------> X ------> X ------> X ---------------------> NULL
X ------> X -> X -> X ------> X -----------> X ------> NULL
X -> X -> X -> X -> X -> X -> X -> X -> X -> X -> X -> NULL
H 5 8 25 28 33 52 55 70 81 83