0
@Getter
@Setter
@AllArgsConstructor
@ToString
public final class StationsDepth {
    private String nameStations;
    private int depth;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        StationsDepth depth = (StationsDepth) o;
        return Objects.equals(nameStations, depth.nameStations);
    }

    @Override
    public int hashCode() {
        return Objects.hash(nameStations);
    }
}

Есть List<StationsDepth> depthList, в котором хранятся станции и их глубина, но попадаются станции с одинаковым именем и разными глубинами.
Необходимо сделать, чтобы повторяющихся станций не было, а если такие встречаются, то оставить те, которые глубже.
Я смог отфильтровать только по именам станций, но не могу понять, как сделать так, чтобы еще добавить условие и по глубине.

List<StationsDepth> listDepth = depthList.stream()
    .distinct()
    .collect(Collectors.toList()); 
2
  • 2
    Вам нужно удалить элементы из существующего списка или получить новый отфильтрованный список? Также хотелось бы заметить, что переопределять метод equals, чтобы сравнение выполнялось только по имени для специфической задачи -- не слишком хорошая идея. Commented 9 мая в 15:18
  • Как должен обрабатываться случай, когда будут несколько станций с одинаковыми именем и максимальной глубиной? Должна остаться только одна станция? Commented 11 мая в 9:42

3 ответа 3

0

В простейшем случае эта задача решается через дополнительную Map<String, StationsDepth>, которая аккумулирует объекты с одинаковым именем и заменяет значение, если объект с таким именем уже был добавлен в мапу но у претендента большая глубина:

    Collection<StationsDepth> result = depthList.stream()
            .collect(
                    Collectors.toMap(
                            StationsDepth::getNameStations,
                            Function.identity(),
                            (o, n) -> o.getDepth() >= n.getDepth() ? o : n)
            ).values();

либо без стримов:

    Map<String, StationsDepth> depthMap = new HashMap<>();
    depthList.forEach(d -> depthMap.merge(
            d.getNameStations(), 
            d, 
            (o, n) -> o.getDepth() >= n.getDepth() ? o : n)
    );
    Collection<StationsDepth> result = depthMap.values();

если результирующая коллекция должна сохранять порядок элементов, который был в изначальном списке, используйте LinkedHashMap

2
  • У вас Collection<StationsDepth> result а мне бы List<StationsDepth> result Commented 9 мая в 13:27
  • ну думаю вам не составит труда решить эту проблему
    – Serodv
    Commented 9 мая в 13:28
0

Если задача состоит именно в удалении элементов из начального модифицируемого списка, следует использовать метод List::removeIf, который корректно и быстро удалит ненужные элементы, не изменяя их порядка. Данный метод был существенно оптимизирован ещё в Java 9 для ArrayList, чтобы избежать квадратичной сложности при удалении многих элементов, см. статью на Хабре по мотивам доклада Тагира Валеева: "Маленькие оптимизации в Java 9-16"

При этом потребуется построить мапу, которая будет содержать информацию об имени и максимальной глубине станции.

Наиболее лаконичный вариант в данном случае будет использовать Collectors.toMap практически так же, как в предыдущем ответе SeroDv:

List<StationsDepth> depthList = ...; //
Map<String, Integer> deepest = depthList
    .stream()
    .collect(Collectors.toMap(
        StationsDepth::getNameStations, 
        StationsDepth::getDepth,
        Integer::max
    ));

depthList.removeIf(sd -> sd.getDepth() < deepest.get(sd.getNameStations()));

Также можно использовать различные варианты Collectors.groupingBy / Collectors.mapping / Collectors.maxBy:

Map<String, Optional<Integer>> deepest2 = depthList
    .stream()
    .collect(Collectors.groupingBy(
        StationsDepth::getNameStations, 
        Collectors.mapping(StationsDepth::getDepth, Collectors.maxBy(Comparator.naturalOrder()))
    ));
depthList.removeIf(sd -> sd.getDepth() < deepest2.get(sd.getNameStations()).get());

Или Collectors.collectingAndThen, чтобы преобразовать Optional, полученный в результате Collectors.maxBy:

Map<String, Integer> deepest3 = depthList
    .stream()
    .collect(Collectors.groupingBy(
        StationsDepth::getNameStations, 
        Collectors.collectingAndThen(
            Collectors.maxBy(
                Comparator.comparingInt(StationsDepth::getDepth)
            ),  // Optional<StationsDepth> 
            r -> r.get().getDepth()
        )
    ));
depthList.removeIf(sd -> sd.getDepth() < deepest3.get(sd.getNameStations()));

Если просто воспользоваться коллекцией значений, которые будут храниться в некой мапе Map<String, StationsDepth> и добавить её в некий новый список, то порядок первоначального списка может быть нарушен, несмотря на использование LinkedHashMap:

Map<String, StationsDepth> mapDeepest = depthList
    .stream()
    .collect(Collectors.groupingBy(
        StationsDepth::getNameStations,
        LinkedHashMap::new,
        Collectors.collectingAndThen(           
            Collectors.maxBy(
                Comparator.comparingInt(StationsDepth::getDepth)
            ), 
            Optional::get
        )
    ));
List<StationsDepth> brokenOrder = new ArrayList<>(mapDeepest.values());

поэтому для сохранения порядка придётся ещё раз пройтись по начальному списку и применить фильтрацию (оставить только максимумы):

List<StationsDepth> goodOrder = depthList
    .stream()
    .filter(sd -> sd.getDepth() == mapDeepest.get(sd.getNameStations()).getDepth())
    .toList() // Java 16+ или привычный Collectors.toList()
;

Замечание: данные способы не удаляют дублированные значения, т.е. когда исходный список содержит несколько станций с одинаковым именем и максимальной глубиной. В таком случае дубликаты можно отфильтровать при помощи уже упоминавшейся операции Stream::distinct (желательно, чтобы методы equals / hashCode были определены корректно):

depthList = depthList.stream().distinct().toList();

Также можно предложить следующий алгоритмический вариант (без Stream API) (благодарность @iramm за идею):

  • построить мапу, хранящую максимальную глубину и индекс первого максимума в массиве, одновременно заменяя "ненужные" значения в списке null-ами (чтобы избежать множественных вызовов метода remove в цикле)
  • сдвинуть ненулловые элементы в начало списка
  • удалить ненужный "хвост":
List<StationsDepth> list = depthList;  // alias

Map<String, int[]> maxes = new HashMap<>();
// первый проход по списку, заполнение мапы и 
for (int i = 0, n = list.size(); i < n; i++) {
    StationsDepth curr = list.get(i);
    int[] max = maxes.get(curr.getNameStations());
    if (max == null) {
        maxes.put(curr.getNameStations(), new int[]{curr.getDepth(), i});
    } else if (curr.getDepth() <= max[0]) { // "<=" для удаления дубликатов
        list.set(i, null);
    } else { // найден новый максимум
        list.set(max[1], null);   // удаляем предыдущий максимум
        max[0] = curr.getDepth();
        max[1] = i;
    }
}
int sz = 0;
for (int i = 0, n = list.size(), m = maxes.size(); i < n && sz < m; i++) {
    if (null != list.get(i)) {
        list.set(sz++, list.get(i));
    }
}
// идиома для удаления подсписка в хвосте
list.subList(sz, list.size()).clear();

Если дубликатов много и размер мапы maxes гораздо меньше размера исходного списка, можно получить результат, отсортировав значения этой мапы по индексу и извлекая несколько нужных значений из оригинала:

List<StationsDepth> result = maxes.values()
    .stream()
    .sorted(Comparator.comparingInt(v -> v[1]))
    .map(v -> list.get(v[1]))
    .collect(Collectors.toList());
-1

Я решила решить задачу без стримов - чисто алгоритмически. Вот код:

        StationsDepth first, second;
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                first = list.get(i);
                second = list.get(j);
                if(first.nameStations.equals(second.nameStations)) {
                    if(first.depth < second.depth) {
                        list.remove(i);
                        list.remove(--j);
                        list.add(i, second);
                    }
                    else {
                        list.remove(j--);
                    }
                }
            }
        }
7
  • 1
    1) Можно удалять по индексу List::remove(int index) -- тогда не потребуется переопределять equals 2) Предложенный алгоритм -- квадратичный. Commented 11 мая в 9:48
  • Спасибо за советы. Исправила.
    – iramm
    Commented 11 мая в 10:57
  • Жаль, но исправленная версия работает некорректно. Commented 11 мая в 12:41
  • На моём наборе данных все работает. Ошибки не нахожу.. Не могли бы вы предоставить данные, при которых происходит ошибка?
    – iramm
    Commented 11 мая в 14:50
  • Пожалуйста, онлайн демо -- вместо ожидаемого результата [{abc=30}, {def=35}] получается [{def=35}, {abc=28}] -- меняется порядок и неправильно вычисляется максимум для одной станции. Также обратите внимание на вопрос "Почему ArrayList.remove(i) в цикле ведёт к квадратичному времени выполнения?", то есть при двух вложенных циклах сложность представленного решения получается кубическая: O(N³) Commented 11 мая в 17:16

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.