如何最有效地在LinkedList中找到max和min元素？

Question

比方说,我有一个Java链表,LinkedList<T> list = new LinkedList<T>();我需要最有效地找到最大/最小元素,我该怎么办呢？

如何使用Collections.max()函数从链表中查找max元素？这个函数的时间复杂度是多少？

Answer 1

时间复杂度O(n)如果您希望它更低,例如O(1)您需要使用不同的数据结构,例如TreeSet.

我如何使用Collections.max()为LinkedList

List<Integer> list = ...
Integer max = Collections.max(list);