31. Next Permutation，下一个排列

Last Updated: 2024-01-05 13:12:46 Friday

-- TOC --

题目分析
思路
Python
C++
C

题目分析

A permutation of an array of integers is an arrangement of its members into a sequence or linear order. For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

排列麻...

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

next lexicographically greater permutation of its integer，这个说法容易歧义，大小比较是在元素之间，而不需要将元素转换为string再比较。

For example, the next permutation of arr = [1,2,3] is [1,3,2]. Similarly, the next permutation of arr = [2,3,1] is [3,1,2]. While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums. The replacement must be in place and use only constant extra memory. 直接修改入参，无返回值。空间复杂度为\(O(1)\)。

Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:
Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:
Input: nums = [1,1,5]
Output: [1,5,1]

Constraints:

1 <= nums.length <= 100

0 <= nums[i] <= 100

思路

最大可能有100个元素，如果遍历所有的排列，想必计算量会非常巨大。

下一个排列，要尽可能的保持靠左边的元素不变，让某个尽可能靠右的元素变大，还不能变得很大，只能用更右边的某个只大一点点的那个元素来替换，然后，右边其它元素，需要重新排个序，从小到大。仔细分析一下就可以观察到，右边的元素，已经是有序的了，只不过是降序，再交换之后，只需要将降序变为升序即可。

Python

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        p1 = p2 = len(nums) - 1
        while p1 > 0:
            if nums[p1-1] < nums[p1]:
                break
            p1 -= 1
        else:
            nums[:] = sorted(nums)
            return 
        p3 = p1 - 1
        while nums[p2] <= nums[p3]:
            p2 -= 1
        nums[p3], nums[p2] = nums[p2], nums[p3]
        nums[p1:] = sorted(nums[p1:])

Python代码的性能，有的时候要测试才能确定具体的写法。下面的测试，确定了sorted是更快的逆序方法：

$ python -m timeit -s 'a=[9,8,7,6,5,4,3,2,1]' -p 'sorted(a)'
1000000 loops, best of 5: 233 nsec per loop
$ python -m timeit -s 'a=[9,8,7,6,5,4,3,2,1]' -p 'list(reversed(a))'
1000000 loops, best of 5: 344 nsec per loop
$ python -m timeit -s 'a=[9,8,7,6,5,4,3,2,1]' -p '[i for i in reversed(a)]'
500000 loops, best of 5: 526 nsec per loop

C++

class Solution {
public:
    void nextPermutation(vector<int>& nums) noexcept{
        size_t p1 { nums.size()-1 };
        size_t p2 { p1 };
        while(p1 > 0){
            if(nums[p1-1] < nums[p1])
                break;
            --p1;
        }
        if(p1 == 0){
            reverse(nums.begin(), nums.end());
            return;
        }
        size_t p3 { p1-1 };
        while(nums[p2] <= nums[p3])
            --p2;
        swap(nums[p2], nums[p3]);
        reverse(nums.begin()+p1, nums.end());
    }
};

C++就直接用内置的reverse了，排序怎么都是非线性的复杂度。

C

static inline void reverse(int *n, int size){
    int t;
    int j = size-1;
    for(int i=0; i<size/2; ++i,--j){
        t = n[i];
        n[i] = n[j];
        n[j] = t; 
    }
}

void nextPermutation(int* nums, int numsSize) {
    int p1, p2;
    p1 = p2 = numsSize - 1;
    while(p1 > 0){
        if(nums[p1-1] < nums[p1])
            break;
        --p1;
    }
    if(p1 == 0){
        reverse(nums, numsSize);
        return;
    }
    int p3 = p1 - 1;
    while(nums[p2] <= nums[p3])
        --p2;
    int t = nums[p3];
    nums[p3] = nums[p2];
    nums[p2] = t;
    reverse(nums+p1, numsSize-p1);
}

C语言就要自己写reverse逻辑...

本文链接：https://cs.pynote.net/ag/leetcode/202312298/

-- EOF --

-- MORE --