Как получить элемент List с минимальным индексом объекта?

Question

[pshevnin]

Добрый день, возможно вопрос слишком тривиальный, но в интернете не нашёл ответа.

Есть лист объектов, у каждого объекта есть свой индекс, как получить объект с минимальным индексом не сортируя лист?

Answer 1

[Николай Савельев]

Первое решение - это простой перебор всех элементов - это О(n), что быстрее сортировки.
Сортировка выполняется за O(n*log(n)) в лучшем случае, а в худшем за О(n^2).
Поэтому сортировка исключается полностью для такой простой задачи.
Есть ещё вариант - при добавлении элементов в список проверять их индекс и запоминать ссылку на объект с минимальным индексом ,который встретился на момент вставки. Если не учитывать момент вставки, то здесь сложность О(1)

Comments

[pshevnin]

спасибо

Answer 2

[Wan-Derer]

как

Например, используя Stream API :)

import java.util.List;
import java.util.Random;
import java.util.stream.Stream;

public class Test {
  public static void main(String[] args) {

    // Create List
    List<MyObj> objects = Stream.generate(MyObj::new).limit(10).toList();
    System.out.println(objects);

    // Get minimal index item
    MyObj minIndexObj = objects
      .stream()
      .reduce((a, b) -> a.getIndex() < b.getIndex() ? a : b).orElse(null);
    
    System.out.println(minIndexObj);

  }
}

class MyObj {
  private final int index;

  public MyObj() {
    index = new Random().nextInt();
  }

  public int getIndex() {
    return index;
  }

  @Override
  public String toString() {
    return "MyObj { index= " + index + " }";
  }
}