Как сортировать элементы при входе в Java

Допустим, нам дан список букв B, F, A, G, и что они расположены друг над другом, и я хочу распечатать порядок, в котором они были расположены друг над другом. Например, если бы мне дали информацию, что :

А-Г / Ф-Б / А-Б / А-Ф / ГБ / Г-Ф

где символ - означает «находится поверх» (так что A находится поверх G, F находится поверх B, A находится поверх B...), тогда я хочу вывести A, G, F, B на основе на приведенных данных. Проблема в том, что этот список читается построчно, поэтому после чтения первой строки ожидаемый вывод будет A, G, пока не будут прочитаны другие строки и ожидаемый вывод не будет обновлен. Моим первым побуждением было использовать стек, но тогда мне потребовалось бы много операций pop и push, и это было бы проблемой, потому что лучшая структура данных позволяла бы мне переключаться местами между буквами или свободно перемещать объекты, а деревья кажутся лучшим вариантом. но как именно это будет реализовано?

Вы можете использовать двусвязный список, если хотите много манипулировать им.

Cayman 02.04.2022 01:55

Все еще не ясно, чего вы хотите, и я не вижу здесь никакой сортировки. И я хочу вывести A, G, F, B. Похоже, вы просто печатаете их в том порядке, в котором они были введены. Также неясно, как предполагается использовать информацию в том виде, в каком она предоставляется. Опубликуйте ожидаемый результат и операции для показанных данных.

WJS 02.04.2022 02:13
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
1
2
59
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Я бы использовал ориентированный граф. В JDK нет классов ориентированного графа, но есть много библиотек, которые его реализуют (перечислены здесь), лично я бы посмотрел на jgrapht или библиотеку Google Guava (не помню, есть ли ориентированный граф). Вот как выглядит ориентированный граф для ваших данных:
Directed Graph

Как только ваш ориентированный граф создан и вы убедитесь, что в нем нет циклов (например, вы не определили A-B, B-C, C-A, что создает цикл), тогда сортировка — это просто вопрос написания компаратора со следующей логикой:

  • если o1 == o2 вернуть 0;
  • если o1 подключен к o2, вернуть -1;
  • если o1 не подключен к o2, вернуть 1;

Вы можете использовать пары для создания компаратора следующим образом:

Set<List<String>> pairs = Arrays.stream(order.split(" / "))
        .map(p -> p.split("-"))
        .map(Arrays::asList)
        .collect(Collectors.toSet());

Comparator<String> compare = (a, b) ->
        pairs.contains(Arrays.asList(a, b)) ? -1 :
        pairs.contains(Arrays.asList(b, a)) ? 1 :
        0;

Затем используйте это, чтобы отсортировать ввод в любой структуре, которую вы хотите.

Идеоне Демо

Другие вопросы по теме