java - LinkedListの最大要素と最小要素を最も効率的に見つける方法は?

Question

たとえば、Java でリンクされたリストがLinkedList<T> list = new LinkedList<T>();あり、その中の最大/最小要素を最も効率的に見つける必要があります。どうすればよいですか?

Collections.max()関数を使用して、リンクされたリストから最大要素を見つけるにはどうすればよいですか? この関数の時間計算量は?

Answer 1

時間の複雑さはO(n)、それを低くしたい場合です。たとえばO(1)、TreeSet などの別のデータ構造を使用する必要があります。

LinkedList に Collections.max() を使用する方法

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));
}
}

---