如何从java中的链表中删除最大元素?我知道我可以使用 get() 或 remove() 函数来检索/删除元素。但我想让它变得高效。我想使用迭代器。你知道我该怎么做吗?请注意,我不想创建自己的链表。我什至不想对我的链接列表进行排序。
我可以对此进行线性搜索吗?如果是这样,我如何跟踪指向最大元素的指针(或迭代器)。任何帮助将不胜感激。
最佳答案
链接列表(除非排序)并不是您在此处尝试执行的操作的最佳结构,因为除了进行线性搜索并删除最大元素之外,您别无选择
Integer biggest = Integer.MIN_VALUE;
for(Integer e : myList){
if(biggest < e)
biggest = e;
}
myList.remove(biggest);
这将是 O(n),即使您必须再次扫描以删除最大的,如果您使用自己的 LinkedList,则第二次扫描是可以避免的,因为 java.util.LinkedList 隐藏了其 Entry 类并且不允许您修改指针;但这将是错误的优化方法,因为如果您使用类似堆的结构,在 java 中将是 PriorityQueue 类,您可以获得 O(log(n)) 并将代码减少为:
return myPriorityQueue.poll();
关于Java链表: Removing Largest Element Using Iterator,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5924994/