java – 我们如何优化ArrayList上的插入?
事实上,这是几天前提出的一个面试问题.
面试官希望我表达ArrayList和LinkedList之间的区别,并要求优化ArrayList上的插入操作,换句话说,重新实现add(int index,E element),当然还有get(int index)的复杂性操作可以牺牲. 我的答案是将数组分成k个子数组并更新一个计数数组,表示相应子数组中已有的元素数.并且每个子数组的内存都以预期的初始大小动态分配.当我需要将数据插入ArrayList时,我可以先找到一个子数组,然后在一个小数组中进行操作. 我相信有更好的解决方案.我确实需要一些建议,谢谢! 解决方法
其中一个解决方案可能是:
> add(int index,E element)总是将元素添加到数组的末尾(你还必须存储应该添加这个元素的索引) – 复杂度O(1)> get(int index)必须恢复数组的正确顺序(如果在最后一次调用后添加了一些元素) – 知道每个元素应该在的位置,你可以在O(n)中恢复正确的顺序 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |