Сортировка массива строк в порядке возрастания суммы значений ASCII символов

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

Дан массив arr[] , состоящий из N строк, задача состоит в том, чтобы отсортировать строки в порядке возрастания суммы значений ASCII их символов.

Примеры:

Input: arr[] = {“for”, “geeks”, “app”, “best”}
Output: app for best geeks
Explanation:
Sum of ASCII values of characters of each string is: {327, 527, 321, 430}.
Hence, the sorted order of strings is {“app”, “for”, “best”, “geeks”}.

Input: arr[] = {“geeksforgeeks”, “a”, “computer”, “science”, “portal”, “for”, “geeks”}
Output: a for geeks portal science computer geeksforgeeks
Explanation:
Sum of ASCII values of characters of each string is: {1381, 97, 879, 730, 658, 327, 527}.
Hence, the sorted order is {“a”, “for”, “geeks”, “portal”, “science”, “computer”, “geeksforgeeks”}.

Подход: Идея состоит в том, чтобы использовать вспомогательный массив для хранения пар строк и их соответствующей суммы значений символов ASCII. Затем отсортируйте массив на основе первого значения в паре, а затем распечатайте отсортированные строки. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте вектор пар V[] для хранения значения строки и самой строки в виде пары.
  • Перебрать диапазон [0, N – 1], используя переменную i :
    • Найдите сумму значений ASCII символов arr[i] и сохраните ее в переменной, скажем, val .
    • Добавьте пару {val, arr[i]} в V .
  • Отсортируйте вектор Von по первому значению в паре.
  • Выполните итерацию в диапазоне [0, n-1] вектора V , используя переменную i :
    • Выведите строки, т.е. v[i].second.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*log(N) + N*M), где M — длина самой длинной строки в массиве arr[] .
Вспомогательное пространство: O(N)

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