31_下一个排列

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
"""
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
"""
# 字典序：对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。
# 例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321

# 第一步：从数组右边开始扫描，直到找到前一个比后一个小的数a
# 第二步：从右边开始扫描，找到比这个数大的数b
# 第三步：交换两个数a,b
# 第四步：对数a后面的数就行排序，，此时求得就为下一个更大的排列


def nextPermutation(nums):
    length = len(nums)
    i = length - 2
    while i>=0 and nums[i+1]<= nums[i]:
        i -= 1
    if i>=0:
        j = length - 1
        while j >=0 and nums[j] <= nums[i]:
            j -= 1
        swap(nums, i, j)
    reverse(nums, i+1)

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

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


nums = [1, 5, 8, 4, 7, 6, 5, 3, 1]
nextPermutation(nums)
print(nums)