Сортировать двумерный массив лексикографически

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

Для двумерного массива arr[] , имеющего N строк переменного размера, задача состоит в том, чтобы отсортировать массив в лексикографическом порядке, т. е. отсортировать каждую строку лексикографически, а затем отсортировать эти отсортированные строки.

Примеры:

Input: arr[][] = { {23}, {59}, {23, 59} }
Output: { {23}, {23, 59}, {59} }
Explanation: The rows are sorted lexicographically.
Here the row {23, 59} is lexicographically smaller than {59} 
because the first element (23) is smaller than 59.
Though {23} and {23, 59} both have 23 as the first element but {23} has only one element.
Hence {23} is lexicographically smaller than {23, 59}

Input: arr[][] = { {3, 2, 5, 6}, {1, 2, 3}, {6, 3}, {5, 4, 2} }
Output: { {1, 2, 3}, {2, 3, 5, 6}, {2, 4, 5}, {3, 6} }

Input: arr[][] = { {3, 2, 5, 6}, {, 2, 3, 5}, {2, 4, 2, 1}, {6, 3, 7, 8} }
Output: { {1, 2, 2, 4}, {1, 2, 3, 5}, {2, 3, 5, 6}, {3, 6, 7, 8} }

Подход: Идея решения проблемы заключается в следующем:

Smallest lexicographical order can be obtained by sorting the elements of each row and first then sorting the whole 2D array based on the lexicographical order of elements in each row.

Выполните следующие шаги, чтобы решить эту проблему:

  • Во-первых, лексикографически отсортируйте каждую строку данного двумерного массива.
  • Отсортируйте весь двумерный массив на основе лексикографического порядка элементов каждой строки. Строка, которая лексикографически меньше, появится первой в отсортированной матрице.
  • Распечатайте двумерный массив.

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

Сложность времени: O(N*M*log(M)), где N — количество строк, M — максимальный размер строки в arr
Вспомогательное пространство: О(1)

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