java - 如何最有效地在 LinkedList 中找到最大和最小元素？

Question

例如，我在 Java 中有一个链表，LinkedList<T> list = new LinkedList<T>();我需要最有效地找到其中的最大/最小元素，我该怎么做？

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

Answer 1

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

我如何将 Collections.max() 用于 LinkedList

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

Answer 2

ArrayList<Integer> numbers = new ArrayList<Integer>();
/* fill with values */
Integer max = Collections.max(numbers);

Answer 3

Java 文档

此方法迭代整个集合，因此它需要与集合大小成正比的时间。（在））

用法

public class Test
{
  public static void main(String args[])
  {
    // create an LinkedList object
    LinkedList<Integer> list = new LinkedList<Integer>();

    // Add elements to LinkedList
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);

    //Use Max Method
    System.out.println(Collections.max(list));
}
}

---

Answer 4

您还可以使用stream.max()获取 LinkedList 的最大值

LinkedList<Integer> linkedList = new LinkedList<>();

linkedList.add(1); linkedList.add(2);
linkedList.add(3); linkedList.add(4);

linkedList.stream().max(Integer::compareTo).ifPresent(System.out::println);

Output: 4