← Static tasks

31. Next Permutation

leetcode medium

#array#csharp#graph#leetcode#medium#sort

Task

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

Например, для arr = [1,2,3] следующие являются всеми перестановками arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

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

Например, следующая перестановка arr = [1,2,3] — это [1,3,2].

Аналогично, следующая перестановка arr = [2,3,1] — это [3,1,2].

В то время как следующая перестановка arr = [3,2,1] — это [1,2,3], потому что [3,2,1] не имеет лексикографически большего переупорядочивания.

Для данного массива целых чисел nums найдите следующую перестановку nums.

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

Пример:

Input: nums = [1,2,3]

Output: [1,3,2]

C# solution

matched/original
public class Solution {
    public void NextPermutation(int[] nums) {
        int i = nums.Length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.Length - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            Swap(nums, i, j);
        }
        Reverse(nums, i + 1);
    }
    private void Reverse(int[] nums, int start) {
        int i = start, j = nums.Length - 1;
        while (i < j) {
            Swap(nums, i, j);
            i++;
            j--;
        }
    }
    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public void NextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.size() - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            Swap(nums, i, j);
        }
        Reverse(nums, i + 1);
    }
    private void Reverse(vector<int>& nums, int start) {
        int i = start, j = nums.size() - 1;
        while (i < j) {
            Swap(nums, i, j);
            i++;
            j--;
        }
    }
    private void Swap(vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Java solution

matched/original
public class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

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

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

JavaScript solution

matched/original
var nextPermutation = function(nums) {
  const len = nums.length;
  let i = len - 2, j = len - 1, k = len - 1;
  while (i >= 0 && nums[i] >= nums[j]) {
    i--;
    j--;
  }
  if (i >= 0) {
    while (nums[i] >= nums[k]) {
      k--;
    }
    [nums[i], nums[k]] = [nums[k], nums[i]];
  }
  twoPointerReverse(j, len-1, nums);
  return nums;
  
  function twoPointerReverse(left, right, nums) {
    while (left < right) {
      let tmp = nums[left];
      nums[left] = nums[right];
      nums[right] = tmp;
      left++;
      right--;
    }
  }   
};

Python solution

matched/original
class Solution:
    def nextPermutation(self, nums):
        i = len(nums) - 2
        while i >= 0 and nums[i + 1] <= nums[i]:
            i -= 1
        if i >= 0:
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1
            self.swap(nums, i, j)
        self.reverse(nums, i + 1)

    def reverse(self, nums, start):
        i, j = start, len(nums) - 1
        while i < j:
            self.swap(nums, i, j)
            i += 1
            j -= 1

    def swap(self, nums, i, j):
        temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp

Go solution

matched/original
func nextPermutation(nums []int) {
    i := len(nums) - 2
    for i >= 0 && nums[i+1] <= nums[i] {
        i--
    }
    if i >= 0 {
        j := len(nums) - 1
        for nums[j] <= nums[i] {
            j--
        }
        swap(nums, i, j)
    }
    reverse(nums, i+1)
}

func reverse(nums []int, start int) {
    i, j := start, len(nums)-1
    for i < j {
        swap(nums, i, j)
        i++
        j--
    }
}

func swap(nums []int, i int, j int) {
    temp := nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}

Explanation

Algorithm

1️⃣

Мы меняем местами числа a[i−1] и a[j]. Теперь у нас есть правильное число на индексе i−1. Однако текущая перестановка ещё не является той перестановкой, которую мы ищем. Нам нужна наименьшая перестановка, которая может быть сформирована с использованием чисел только справа от a[i−1]. Следовательно, нам нужно расположить эти числа в порядке возрастания, чтобы получить их наименьшую перестановку.

2️⃣

Однако, вспомните, что, сканируя числа справа налево, мы просто уменьшали индекс, пока не нашли пару a[i] и a[i−1], где a[i] > a[i−1]. Таким образом, все числа справа от a[i−1] уже были отсортированы в порядке убывания. Более того, обмен местами a[i−1] и a[j] не изменил этот порядок.

3️⃣

Поэтому нам просто нужно перевернуть числа, следующие за a[i−1], чтобы получить следующую наименьшую лексикографическую перестановку.

😎