Сортировать N троек

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

Дан массив arr[ ] из N триплетов, задача состоит в том, чтобы упорядочить триплеты в порядке убывания. Триплет X будет иметь более высокий приоритет, чем триплет Y , тогда и только тогда, когда все элементы триплета X будут больше или равны соответствующему элементу триплета Y. Print Impossible , если триплеты нельзя упорядочить.

Примеры:

Input: arr = {{1, 2, 3}, {1, 3, 4}, {4, 7, 4}}
Output: {{4, 7, 4}, {1, 3, 4}, {1, 2, 3}}
Explanation:
As it can be seen, all the corresponding elements of triplet C are greater than or equal to triplet B, and all the corresponding elements of triplet B are greater than or equal to triplet A.

Input: arr = {{1, 2, 3), {1, 2, 4}, {1, 3, 1}, {10, 20, 30}, {16, 9, 25}}
Output: Impossible

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

  • Создайте три списка кортежей x , y , и з .
  • Список x, y, z сохранит триплеты с их идентификатором триплета.
  • Сортировать x на основе 1-го элемента триплета.
  • Сортировка y по второму элементу тройки.
  • Сортировать z по 3-му элементу тройки.
  • Итерировать для i в диапазоне [0, N-1] , проверить все i , если x[i][3] = y[i][3] = z[i][3] , затем вывести соответствующий порядок, иначе напечатать «Невозможно».

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(NlogN)
Вспомогательное пространство: O(N)

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