其实这是前几天问的面试题。
面试官要我表达 和 的区别ArrayList，LinkedList并要求优化插入操作ArrayList，换句话说，重新实现add(int index, E element)，当然get(int index)可以牺牲操作的复杂性。
我的答案是将数组分成 k 个子数组并更新一个计数数组，该数组表示相应子数组中已有的元素数。并且每个子数组的内存都是以预期的初始大小动态分配的。当我需要向 中插入数据时ArrayList，我可以先定位一个子数组，然后在一个小数组内进行操作。并且如果插入不是太频繁或者索引是均匀分布的，插入的时间复杂度可以是O(log(k) + n/k + k)平均的，这log(k)意味着我们应该首先对计数数组的和数组进行二进制搜索来定位子数组，n/k用于数据移动甚至内存重新分配，k代表sum数组的更新。
我确信有更好的解决方案。我确实需要一些建议，谢谢！
解决方案之一可能是：
add(int index, E element)总是将元素添加到数组的末尾（您还必须存储应该添加该元素的索引） - 复杂度 O(1)get(int index)必须恢复数组的正确顺序（如果在最后一次调用之后添加了一些元素） - 知道每个元素应该在的位置，您可以在 O(n) 中恢复正确的顺序您可以在平衡二叉树中实现它，这样 add() 和 get() 的成本都是 O(logn)
一个示例实现将如下所示（此处为手工制作，不会编译，未涵盖极端情况）：
class Node {
int subTreeSize;
Node left,right;
Element e;
// all i 0-indexed
Node get(int i) {
if (i >= subTreeSize) {
return null;
}
if (left != null) {
if(left.subTreeSize > i) {
return left.get(i);
} else {
i -= left.subTreeSize;
}
}
if (i == 0) {
return this;
}
return right.get(i-1);
}
// add e to the last of the subtree
void append(Element e) {
if(right == null){
right = new Node(e);
} else {
right.append(e);
right = right.balance();
}
subTreeSize += 1;
}
// add e to i-th position
void add(int i, Element e) {
if (left != null) {
if(left.subTreeSize > i) {
add(i,left);
left=left.balance();
} else {
i -= left.subTreeSize;
}
}
if (i == 0) {
if (left == null){
left = new Node(e);
} else {
left.append(e);
left = left.balance();
}
} else {
if (right == null) {
// also in this case i == 1
right = new Node(e);
} else {
right.add(i-1, e);
right = right.balance();
}
}
subTreeSize += 1;
}
// the common balance operation used in balance tree like AVL or RB
// usually just left or right rotation
Node balance() {
...
}
}
public class Tree {
Node root;
public Element get(int i) {
return root.get(i).e;
}
public void add(int i, Element e) {
if (root == null) {
root = new Node(e);
} else {
root.add(i,e);
root = root.balance();
}
}
}
订单统计树的变体将允许您按 O(log n) 中的索引添加和获取。
基本思路如下：
节点的索引将对应于它在树的有序遍历中的位置。
这意味着节点的顺序是根据它们在树中出现的位置确定的——这不是二叉搜索树通常的工作方式，其中节点的元素具有一些不依赖于它出现在树中的位置的顺序（ egf大于a按字典顺序排序的常规 BST，但在我们的例子f中可能小于或大于a，因为它是根据 和 的索引排序的。fa
要添加或获取，我们从根开始并递归地遍历树，根据目标索引和子树大小确定我们的插入或查找位置是在左侧还是右侧。
更具体地说，我们有以下递归定义：（
对于空节点和实际插入节点增加了一些复杂性）
node.add(index, element):
if index <= left.subtreeSize
left.add(index, element)
else
// anything to the right is after left subtree and current node, so those must be excluded
right.add(index - left.subtreeSize - 1, element)
node.get(index, element):
if index == left.subtreeSize
return node
if index < left.subtreeSize
return left.get(index)
else
return right.get(index - left.subtreeSize - 1)
为了更好地理解这一点，以下示例树可能会有所帮助：
Values: Indices (in-order pos): Subtree sizes:
a 5 8
/ \ / \ / \
b g 1 6 5 2
/ \ \ / \ \ / \ \
f c h 0 3 7 1 3 1
/ \ / \ / \
e d 2 4 1 1
例如，如果我们想在位置 5 插入一个新节点，它将被插入到d.
下面是一个小测试程序来演示这一点（创建上面显示的树）。
请注意，仍然需要进行平衡以实现每个操作的 O(log n) 运行时间。
class Test
{
static class Node<T>
{
Node<T> left, right;
T data;
int subtreeCount;
Node(T data) { this.data = data; subtreeCount = 1; }
public String toString(int spaces, char leftRight)
{
return String.format("%" + spaces + "s%c: %s\n", "", leftRight, data.toString())
+ (left != null ? left.toString(spaces+3, 'L') : "")
+ (right != null ? right.toString(spaces+3, 'R') : "");
}
int subtreeSize(Node<T> node)
{
if (node == null)
return 0;
return node.subtreeCount;
}
// combined add and get into 1 function for simplicity
// if data is null, it is an get, otherwise it's an add
private T addGet(int index, T data)
{
if (data != null)
subtreeCount++;
if (index == subtreeSize(left) && data == null)
return this.data;
if (index <= subtreeSize(left))
{
if (left == null && data != null)
return (left = new Node<>(data)).data;
else
return left.addGet(index, data);
}
else if (right == null && data != null)
return (right = new Node<>(data)).data;
else
return right.addGet(index-subtreeSize(left)-1, data);
}
}
static class TreeArray<T>
{
private Node<T> root;
public int size() { return (root == null ? 0 : root.subtreeCount); }
void add(int index, T data)
{
if (index < 0 || index > size())
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
if (root == null)
root = new Node<>(data);
else
root.addGet(index, data);
}
T get(int index)
{
if (index < 0 || index >= size())
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
return root.addGet(index, null);
}
@Override
public String toString() { return root == null ? "Empty" : root.toString(1, 'X'); }
}
public static void main(String[] args)
{
TreeArray<String> tree = new TreeArray<>();
tree.add(0, "a");
tree.add(0, "b");
tree.add(1, "c");
tree.add(2, "d");
tree.add(1, "e");
tree.add(0, "f");
tree.add(6, "g");
tree.add(7, "h");
System.out.println("Tree view:");
System.out.print(tree);
System.out.println("Elements in order:");
for (int i = 0; i < tree.size(); i++)
System.out.println(i + ": " + tree.get(i));
}
}
这输出：
Tree view:
X: a
L: b
L: f
R: c
L: e
R: d
R: g
R: h
Elements in order:
0: f
1: b
2: e
3: c
4: d
5: a
6: g
7: h
现场演示。
LinkedList 是一个链表，访问\插入\删除需要 O(n)，链表支持顺序访问 O(n)。
ArrayList 是一个数组，插入\删除需要 O(2n)，但访问需要 O(1)，数组支持随机访问 O(1)。
要找到更优化的混合结构，您可以从以下开始：
template <T>
public class LinkedArrayList
{
LinkedList<ArrayList<T>> list;
public LinkedArrayList ()
{
list = new LinkedList<ArrayList<T>> ();
}
// ..
}
您必须在访问复杂性和插入\删除复杂性之间平衡列表中的段（数组）