Permutations

Средняя№46перестановки

Дан список разных чисел. Нужно вернуть все порядки, в которых они могут стоять, каждый по разу, в любом порядке. Наш пример: у [4, 5, 6] 3! = 6 перестановок, от [4, 5, 6] до [6, 5, 4].

46 PermutationsРазбор · 1×

Пример: все перестановки [4, 5, 6], собранные обменами в самом списке. Смотрите на корень: после каждой ветки второй обмен возвращает список к [4, 5, 6], а обмен 4 и 6 даёт [6, 5, 4] раньше, чем [6, 4, 5].

[ ]44,54,5,64,64,6,555,45,4,65,65,6,466,56,5,46,46,4,5nums041526результаты—
ещё не были; позиция свободнапо пути сюда; позиция закрепленаэтот шаг; два числа, которые меняемсохранённый порядокзавершено

Ищем все перестановки [4, 5, 6]

01/57
сначала · назад · пуск · шаг
Скорость
1function permute(nums):
2 results = []
3 arrange(0)
4 return results
5
6function arrange(start):
7 if start == len(nums):
8 add copy of nums to results
9 return
10 for i from start to len(nums) - 1:
11 swap nums[start], nums[i] // nums[i] to start
12 arrange(start + 1)
13 swap nums[start], nums[i] // undo
состояние
start
–
i
–
nums
[4, 5, 6]
results
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Часть до start закреплена; обмен каждого из nums[start..] на позицию start пробует там каждое ещё свободное число по одному разу, поэтому каждый порядок собирается ровно один раз.
  2. Второй обмен отменяет первый: когда вызов вернулся, список ровно такой, каким был, поэтому следующий i меняет числа в том же порядке, и ни одно число не теряется и не повторяется.
  3. Когда start доходит до конца, все позиции закреплены и сам список — один из порядков: сохраняется его копия.

Сложность

Время O(n × n!): n! порядков, каждый копируется за n шагов; вызовы над листьями добавляют меньше этого. Память O(n) помимо ответа: обмены идут в самом списке, а стек вызовов глубиной n.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.