事实上,这是几天前提出的一个面试问题.
面试官要我表达之间的区别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数组的更新.
我相信有更好的解决方案.我确实需要一些建议,谢谢!