31. Next Permutation
Перестановка arrayа целых чисел — это упорядочивание его elementов в последовательность или линейный порядок.
НаExemplo, для arr = [1,2,3] следующие являются всеми перестановками arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
Следующая перестановка arrayа целых чисел — это следующая лексикоgrafoически большая перестановка его чисел. Более формально, если все перестановки arrayа отсортированы в одном контейнере по лексикоgrafoическому порядку, то следующая перестановка этого arrayа — это перестановка, следующая за ней в отсортированном контейнере. Если такое упорядочивание невозможно, array должен быть переупорядочен в наименьший возможный порядок (то есть отсортирован по возрастанию).
НаExemplo, следующая перестановка arr = [1,2,3] — это [1,3,2].
Аналогично, следующая перестановка arr = [2,3,1] — это [3,1,2].
В то время как следующая перестановка arr = [3,2,1] — это [1,2,3], потому что [3,2,1] не имеет лексикоgrafoически большего переупорядочивания.
Для данного arrayа целых чисел nums find следующую перестановку nums.
Замена должна быть выполнена на месте и использовать только постоянную дополнительную память.
Exemplo:
Input: nums = [1,2,3]
Output: [1,3,2]
C# solução
correspondente/originalpublic 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++ solução
rascunho automático, revisar antes de enviar#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 solução
correspondente/originalpublic 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 solução
correspondente/originalvar 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 solução
correspondente/originalclass 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] = tempGo solução
correspondente/originalfunc 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
}Algorithm
1️⃣
Мы меняем местами числа a[i−1] и a[j]. Теперь у нас есть правильное number на индексе 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], чтобы получить следующую наименьшую лексикоgrafoическую перестановку.
😎
Vacancies for this task
vagas ativas with overlapping task tags are mostradas.