Сортировать данное предложение на основе целого числа, присутствующего в каждой строке

Опубликовано: 21 Сентября, 2022

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

Примеры:

Input : {"2a", "grea3t", "l3earning", "geeksfor0geeks", "p10latform", "is1"}
Output: geeksfor0geeks is1 2a grea3t l3earning p10latform

Explanation: Since order of integer parts are: 0, 1, 2, 3, 3, 10
therefore the order of string must be:
geeksfor0geeks, is1, 2a, grea3t, l3earning, p10latform.
Input : {"love9", "i8s", "In5dia"}
Output: In5dia i8s love9

Подход 1: Задачу можно решить с помощью жадного алгоритма . мы создадим список пар , первое значение пар будет содержать целую часть строки, а второе значение пар будет содержать строку как есть, а затем мы отсортируем этот список пар в порядке возрастания, чтобы строка, имеющая целое с меньшим значением будет раньше в списке. выполните следующие шаги, чтобы решить проблему:

  • Создайте список пар, скажем, A , в паре 1-е значения будут целым числом в строке, а 2- е значение будет строкой как есть.
  • Упорядочить А в порядке возрастания.
  • Перебрать каждую пару A и вывести второе значение пары .

Time Complexity: O(N*M*log(N)), where N is the length of JumbledList and M is the string length. (N*log(N) for sorting/multimap.)

Auxiliary Space: O(N*M)

Подход 2 : мы можем использовать словарь для хранения индекса строки во время итерации по JumbledList, где ключ будет строкой, а значение будет индексом (можно также использовать строку как значение и индекс как ключ).

  • Создайте словарь/хэш-карту, как указано выше.
  • Создайте пустой список именно такого размера, как исходный JumbledList.
  • Переберите элементы словаря и назначьте строки (ключи) для индекса (значения) в созданном выше списке.

Time Complexity: O(N*M), where N is the length of JumbledList and M is the string length.

Auxiliary Space: O(N*M)

РЕКОМЕНДУЕМЫЕ СТАТЬИ