Как заказать строковые данные LinkedList - PullRequest
0 голосов
/ 05 ноября 2018

Как я могу заказать LinkedList, который включает тип строки {a,c,d,b,b,d,c,a,c}. После заказа вывод должен быть примерно таким {c,c,c,a,a,d,d,b,b}. Также сложность должна быть O (1 * n).

Ответы [ 3 ]

0 голосов
/ 05 ноября 2018

Это для системы управления запасами. Есть 4 типа данных а, б, в и д

Итак, вам нужно добавить это в ваш пост (также объясните сценарий, если это возможно).

Алгоритм

  • Поскольку вы сказали, что существует только 4 типа данных, поддерживайте 8 переменных - по 2 на тип данных для узлов a, b, c, d, как показано ниже.
Node head_c = null,tail_c = null;
Node head_a = null,tail_a = null;
Node head_d = null,tail_d = null;
Node head_b = null,tail_b = null;
  • Теперь перебирайте связанный список, и всякий раз, когда вы получаете c, делайте, как показано ниже.
if(head_c == null){
   head_c = current_node;
}else{
   tail_c.next = current_node;
}
tail_c = current_node;
  • Сделайте то же самое, что и выше, для других узлов a, d, b тоже. Здесь мы пытаемся создать 4 отдельных списка c, a, d, b отдельно, используя узлы same (same hashCode) связанного списка.

  • Теперь, как вы, наверное, поняли, все, что нужно сделать, это назначить свой хвост голове другого списка для каждого из списков. Увидеть ниже.

main_head = head_c;
tail_c.next = head_a;
tail_a.next = head_d;
tail_d.next = head_b;
tail_b.next = null;
  • Итак, вы получили группу c, a, d, b, которая вам нужна.
  • Сложность времени - O (n) , Сложность пространства: O (1) .
0 голосов
/ 05 ноября 2018

Если вы используете Java 8, вы можете использовать stream(). Посмотрите следующий код:

Сортировка данных с этим:

linkedList.stream().sorted().collect(Collectors.toList())

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

linkedList.stream().sorted(Collections.reverseOrder()).collect(Collectors.toList())
0 голосов
/ 05 ноября 2018

Я предполагаю, что групп / имен / элементов всегда четыре и всегда c, a, d и b. В этом предположении это легко: создать четыре списка, один для элементов c, один для элементов a и т. Д. Пройдите по связанному списку; для каждого элемента добавьте его в соответствующий новый список. Вы можете использовать switch в строках. Наконец добавьте четыре новых списка в правильном порядке.

Это займет O (n) время и O (n) пространство.

Если по какой-то причине (я не знаю, что это может быть) вы не хотите создавать четыре списка, просто сохраните четыре ссылки на четыре места в отсортированном списке, где c, a, d и b элементы должны быть вставлены. Это потребует решения о том, куда указывать, если в списке еще нет всех четырех имен.

Удачного кодирования.

...