Практика быстрого собеседования
Проблема с литкодом 31. Следующая перестановка просит нас переставить список чисел в лексикографически следующую перестановку этого списка чисел.
Наивное решение
Обычно наивное решение оказывается достаточно простым, но в данном случае это неверно. Чтобы попытаться получить список всех перестановок целых чисел.
Одним из решений этого является взять любое число в качестве первого числа и добавить его к перестановкам любых других чисел, что даст нам список перестановок. Закажите их и выберите следующую доступную перестановку, которая требует от нас сортировки списка перестановок.
Наивный код — на Swift
Примечание. Код для этого на самом деле такой же сложный, как и для более эффективного решения. Этот код также работает слишком долго для довольно жестких временных ограничений LeetCode на эту проблему.
Алгоритм Нараяны Пандиты — псевдокод
Например
1,2,3 при перестановке могут быть в альтернативном порядке (3,2,1; 3,1,2; 2,1,3; 2,3,1; 1,3,2) и из этих 1,3 ,2 является «следующим» после 1,2,3 из перечисленных выше альтернативных вариантов.
Алгоритм существует (из Википедии)
- Найдите наибольший индекс k такой, что a[k] ‹ a[k + 1]. Если такого индекса нет, данная перестановка является последней перестановкой (и проблема LeetCode требует, чтобы мы возвращали отсортированный массив). Мы находим индекс неуместным, чтобы эта перестановка не была последней.
- Найдите наибольший индекс i, больший k, такой, что a[k] ‹ a[i]. Найти элемент в правой части массива
Алгоритм Нараяны Пандиты — схематично
Код — на Swift
Хотите связаться? Свяжитесь с нами в Твиттере:
