LeetCode: Следующая перестановка

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

Задача leetCode #31 (средний): следующая перестановка

31. Следующая перестановка

Реализация Следующая перестановка , который переставляет числа в лексикографически следующую большую перестановку чисел.

Если такое расположение невозможно, оно должно изменить его как самый низкий возможный порядок (то есть отсортированный в порядке возрастания).

Замена должна быть на месте и использовать только постоянную дополнительную память.

Пример 1:

Ввод: Nums = [1,2,3] Вывод: [1,3,2]

Пример 2:

Ввод: Nums = [3,2,1] Вывод: [1,2,3]

Пример 3:

Ввод: Nums = [1,1,5] Вывод: [1,5,1]

Пример 4:

Ввод: Nums = [1] Вывод: [1]

Ограничения:

1.length 0 [i]

Решение

Идея немного сложна, прежде всего, ответ не является числом, а перестройка цифр, показанных в входном массиве. Это может дать нам намек на то, что нам не нужно рассчитать число по индексу 10.

или

Вы можете подумать об этом решении как о грубой силе:

• создать все перестановки ввода,
• генерировать число из этого входного варианта,
• Найдите следующий по величине на этот момент, вы можете подумать о хранении массива в качестве индекса HashMap и числа в качестве его значения

И в этом нет ничего плохого, за исключением времени выполнения O (n x n!) – КАКАЯ!

Итак, мы сразу же должны обратиться к какому -либо другому подходу – действительно ли нам нужно рассчитать Все перестановки!

Посмотрим из примера:

Вход = [1, 2, 3] Решение = [1, 3, 2]

Можем ли мы сказать, что мы просто разбавляем более крупную цифру с непосредственной меньшей справа?

Хорошо, но это не будет работать каждый раз

Вход = [1, 3, 2] Решение = [2, 1, 3]

Только Трюк, необходимый здесь: Мы начинаем справа – сравниваем две цифры до тех пор, пока не найдем индекс, который меньше 2, то есть мы сравниваем N -1, пока не достигнем левого или неудачного случая.

для [1, 3, 2] Мы достигли до я (1)

Теперь, если мы достигли -1 -> Мы не можем создать большее число, благодаря оператору проблемы, мы просто отменим число и возвращаем.

но если я , мы снова начинаем с конца (скажем, J ), пока не найдем число больше чем я 2 Итак, J (2)

Мы обмениваемся i J [2, 3, 1]

И последний шаг мы Обратный Все цифры после индекса ITH (i+1) 2 [3, 1] -> 2 [1, 3]

Реализация:

    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;

        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }

        if (i >= 0) {
            while (nums[j] <= nums[i]) {
                j--;
            }

            swap(nums, i, j);
        }

        reverse(nums, i + 1);
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private static void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

** Бонус Так как некоторые из вас любят Python -> наслаждаться;)

def next_perm(n):
    i = len(n) - 2
    while i >= 0 and n[i + 1] <= n[i]:
        i -= 1

    if i >= 0:
        j = len(n) - 1
        while n[j] <= n[i]:
            j -= 1

        swap(n, i, j)

    return reverse(n, i + 1)


def swap(n, i, j):
    n[i], n[j] = n[j], n[i]


def reverse(n, from_index):
    res = []
    for i in range(0, from_index):
        res.append(n[i])

    for i in range(len(n) - 1, from_index - 1, -1):
        res.append(n[i])

    return res

Оригинал: “https://dev.to/saurabhpro/solution-next-permutation-4711”