Решение задачи 31 “Next Permutation” с LeetCode.
Условие задачи
Необходимо реализовать следующую перестановку, которая отсортирует число в лексикографическом порядке для следующей перестановки чисел.
Если такая перестановка невозможна - необходимо отсортировать числа по возрастанию.
замечание
перестановка должна осуществляться внутри массива и использовать константную память
пример
1
2
3
|
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
|
Решение
Найти перестановку
Идея такая..
-
идти с конца массива.
Взять текущее элемент и идти в начало, по неубывающей последовательности. Как только встретиться элемент ломающий неубывающую последовательность - запомнить его индекс.
-
Потом идти вправо от этого элемента в поисках элемента, который больше текущего на минимальное значение. Как нашли - поменять эти два элемента местами. А все элементы справа от текущего отсортировать по возрастанию.
-
опциональный, если в первом пунктке ничего не нашли - осортровать массив по возврстанию
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
func nextPermutation(nums []int) {
ordered := false
pos := len(nums)-1
for idx := len(nums)-1; idx>=0; idx--{
if ordered {
continue
}
for jdx := idx; jdx>0; jdx -- {
if !ordered && nums[jdx-1]<nums[jdx]{
ordered = true
pos = jdx-1
}
}
}
if ordered {
maxdist := math.MaxInt32
maxpos := pos
for idx:= pos+1; idx<len(nums);idx++ {
if nums[idx]>nums[pos] && nums[idx]-nums[pos]<maxdist {
maxdist = nums[idx]-nums[pos]
maxpos = idx
}
}
nums[maxpos], nums[pos] = nums[pos], nums[maxpos]
pos++
for idx:= pos; idx<len(nums);idx++ {
k := idx
for jdx := idx;jdx>=pos;jdx-- {
if nums[k]<nums[jdx]{
nums[k], nums[jdx] = nums[jdx], nums[k]
k=jdx
}
}
}
}
if !ordered {
for idx := len(nums)-1; idx>=0; idx--{
for jdx := idx; jdx>=0; jdx -- {
if nums[idx]<nums[jdx]{
nums[idx], nums[jdx] = nums[jdx], nums[idx]
ordered = true
}
}
}
}
}
|