Постановка задачи
Реализуйте следующую перестановку, которая переставляет числа в лексикографически следующую большую перестановку чисел.
Если такое расположение невозможно, оно должно быть перестроено как самый низкий возможный порядок (т. е. отсортировано в порядке возрастания).
Замена должна быть на месте и использовать только постоянную дополнительную память.
Постановка задачи взята с: https://leetcode.com/problems/next-permutation
Пример 1:
Input: nums = [1, 2, 3]
Output: [1, 3, 2]
Пример 2:
Input: nums = [3, 2, 1]
Output: [1, 2, 3]
Пример 3:
Input: nums = [1, 1, 5]
Output: [1, 5, 1]
Пример 4:
Input: nums = [1]
Output: [1]
Ограничения:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
Объяснение
Подход грубой силы
Подход грубой силы заключается в том, чтобы найти все возможные перестановки элементов массива и выяснить перестановку, которая является следующей по величине.
Проблема здесь в том, что мы генерируем все перестановки элементов массива, и это занимает много времени.
Временная сложность этого подхода составляет O(N!), а пространственная сложность — O(N).
Однопроходный подход
Для данной последовательности, которая находится в порядке убывания, как показано ниже
[8, 5, 3, 2, 1]
следующая большая перестановка невозможна. Это дает нам подсказку по определению следующей большей перестановки.
Нам нужно найти первую пару из двух последовательных чисел nums[i] и nums[i − 1] справа, которые удовлетворяют nums[i] › числа[i − 1].
Как только мы найдем индекс i — 1, нам нужно заменить число nums[i — 1] на число, которое чуть больше его самого среди чисел, лежащих в его правая часть nums[i]..nums[nums.size() — 1], скажем, nums[j].
Мы меняем местами числа nums[i — 1] и nums[j]. Мы переворачиваем все числа из индекса i и nums.size() — 1.
Алгоритм
- return if nums.size() <= 1
- set n = nums.size(), i = n - 1
- loop while i > 0
- if nums[i] > nums[i - 1]
- break
- if i <= 0
- i = 0
- set x = ( i == 0 ) ? nums[i] : nums[i - 1]
- smallest = i
- loop for j = i + 1; j < n; j++
- nums[j] > x && nums[j] < nums[smallest]
- smallest = j
- swap(&nums[smallest], (i == 0 ? &nums[i] : &nums[i - 1]));
- sort(nums.begin() + i, nums.end());
Решение C++
class Solution {
public: void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
public:
void nextPermutation(vector<int>& nums) {
if(nums.size() <= 1){
return;
}
int n = nums.size();
int i = n - 1;
for(;i > 0; i--){
if(nums[i] > nums[i-1])
break;
}
if(i <= 0){
i = 0;
}
int x = (i == 0 ? nums[i] : nums[i - 1]);
int smallest = i;
for(int j = i + 1; j < n; j++){
if(nums[j] > x && nums[j] < nums[smallest])
smallest = j;
}
swap(&nums[smallest], (i == 0 ? &nums[i] : &nums[i - 1]));
// we can also use reverse
sort(nums.begin() + i, nums.end());
}
};
Решение Golang
func reverse(nums []int) {
for i := 0; i < len(nums); i++ {
j := len(nums) - 1 - i
if i >= j {
break
}
nums[i], nums[j] = nums[j], nums[i]
}
}
func nextPermutation(nums []int) {
i := 0
for i = len(nums) - 2; i >= 0; i-- {
if nums[i] < nums[i + 1] {
break
}
}
if i == -1 {
reverse(nums)
return
}
var j int
for j = len(nums)-1; j > i; j-- {
if nums[j] > nums[i] {
break
}
}
nums[i], nums[j] = nums[j], nums[i]
reverse(nums[i + 1:])
}
Решение для JavaScript
var nextPermutation = function(nums) {
if (nums === null || nums.length === 0) {
return nums;
}
let index = -1;
for (let i = nums.length - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
index = i;
break;
}
}
if (index >= 0) {
for (let i = nums.length - 1; i > index; i--) {
if (nums[i] > nums[index]) {
let temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
break;
}
}
}
let start = index + 1;
let end = nums.length - 1;
while (start < end) {
let temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
};
Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.
Input: nums = [1, 2, 3, 6, 5, 4]
Output: [1, 2, 4, 3, 5, 6]
Step 1: nums.size() <= 1
6 <= 1
false
Step 2: n = nums.size()
n = 6
i = n - 1
= 6 - 1
= 5
Step 3: loop for i > 0
5 > 0
true
if nums[i] > nums[i - 1]
nums[5] > nums[4]
4 > 5
false
i--
i = 4
Step 4: loop for i > 0
4 > 0
true
if nums[i] > nums[i - 1]
nums[4] > nums[3]
5 > 6
false
i--
i = 3
Step 5: loop for i > 0
3 > 0
true
if nums[i] > nums[i - 1]
nums[3] > nums[2]
6 > 3
true
break
Step 6: i <= 0
3 <= 0
false
Step 7: x = (i == 0 ? nums[i] : nums[i - 1])
= (3 == 0 ? nums[3] : nums[2])
= (false ? nums[3] : nums[2])
= nums[2]
= 3
smallest = i
= 3
Step 8: loop for(j = i + 1; j < n; j++)
j = 3 + 1
= 4
j < n
4 < 6
true
nums[j] > x && nums[j] < nums[smallest]
nums[4] > 3 && nums[4] < nums[3]
5 > 3 && 5 < 6
true
smallest = j
= 4
j++
j = 5
Step 9: loop for(j = i + 1; j < n; j++)
j < n
5 < 6
true
nums[j] > x && nums[j] < nums[smallest]
nums[5] > 3 && nums[5] < nums[4]
4 > 3 && 4 < 6
true
smallest = j
= 5
j++
j = 6
Step 10: loop for(j = i + 1; j < n; j++)
j < 6
6 < 6
false
Step 11: swap(&nums[smallest], (i == 0 ? &nums[i] : &nums[i - 1]));
swap(&nums[5], 3 == 0 ? &nums[3] : &nums[2])
swap(&nums[5], &nums[2])
swap(3, 4)
[1, 2, 4, 6, 5, 3]
Step 12: reverse(nums[i], nums[n - 1])
reverse(nums[3], nums[5])
[1, 2, 4, 3, 5, 6]
Первоначально опубликовано на https://alkeshghorpade.me.