Задача: 31. Next Permutation
Сложность: medium

Перестановка массива целых чисел — это упорядочивание его элементов в последовательность или линейный порядок.

Следующая перестановка массива целых чисел — это следующая лексикографически большая перестановка его чисел. Если такое упорядочивание невозможно, массив должен быть переупорядочен в наименьший возможный порядок (отсортирован по возрастанию).

Пример:

Input: nums = [1,2,3]  
Output: [1,3,2]  

👨‍💻Алгоритм:

1⃣Найти первое число nums[i], которое меньше nums[i+1], двигаясь справа налево.

2⃣Найти наименьшее число справа от nums[i], которое больше него, и поменять их местами.

3⃣Перевернуть все элементы после i, чтобы получить наименьшую возможную лексикографическую перестановку.

😎Решение:

func nextPermutation(_ nums: inout [Int]) {
    var i = nums.count - 2
    while i >= 0 && nums[i + 1] <= nums[i] {
        i -= 1
    }
    if i >= 0 {
        var j = nums.count - 1
        while nums[j] <= nums[i] {
            j -= 1
        }
        nums.swapAt(i, j)
    }
    reverse(nums: &nums, start: i + 1)
}

func reverse(nums: inout [Int], start: Int) {
    var i = start
    var j = nums.count - 1
    while i < j {
        nums.swapAt(i, j)
        i += 1
        j -= 1
    }
}

Ставь 👍 и забирай 📚 Базу знаний