面试官希望我表达ArrayList和LinkedList之间的区别,并要求优化ArrayList上的插入操作,换句话说,重新实现add(int index,E element),当然还有get(int index)的复杂性操作可以牺牲.

我的答案是将数组分成k个子数组并更新一个计数数组,表示相应子数组中已有的元素数.并且每个子数组的内存都以预期的初始大小动态分配.当我需要将数据插入ArrayList时,我可以先找到一个子数组,然后在一个小数组中进行操作.
如果插入不是太频繁或索引是均匀分布的,插入的时间复杂度平均可以是O(log(k)n / kk),其中log(k)意味着我们应该首先用二进制定位子数组在计数数组的和数组上搜索,n / k用于数据移动或甚至是存储器重新分配,k代表和数组的更新.

我相信有更好的解决方案.我确实需要一些建议,谢谢！