Skip to content

Latest commit

 

History

History
310 lines (273 loc) · 8.84 KB

0031.下一个排列.md

File metadata and controls

310 lines (273 loc) · 8.84 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

31.下一个排列

力扣题目链接

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

示例 1：

  • 输入：nums = [1,2,3]
  • 输出：[1,3,2]

示例 2：

  • 输入：nums = [3,2,1]
  • 输出：[1,2,3]

示例 3：

  • 输入：nums = [1,1,5]
  • 输出：[1,5,1]

示例 4：

  • 输入：nums = [1]
  • 输出：[1]

思路

一些同学可能手动写排列的顺序，都没有写对，那么写程序的话思路一定是有问题的了，我这里以1234为例子，把全排列都列出来。可以参考一下规律所在：

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

如图：

以求1243为例，流程如图：

对应的C++代码如下：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        for (int i = nums.size() - 1; i >= 0; i--) {
            for (int j = nums.size() - 1; j > i; j--) {
                if (nums[j] > nums[i]) {
                    swap(nums[j], nums[i]);
                    reverse(nums.begin() + i + 1, nums.end());
                    return;
                }
            }
        }
        // 到这里了说明整个数组都是倒序了，反转一下便可
        reverse(nums.begin(), nums.end());
    }
};

其他语言版本

Java

class Solution {
    public void nextPermutation(int[] nums) {
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = nums.length - 1; j > i; j--) {
                if (nums[j] > nums[i]) {
                    // 交换
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    // [i + 1, nums.length) 内元素升序排序
                    Arrays.sort(nums, i + 1, nums.length);
                    return;
                }
            }
        }
        Arrays.sort(nums); // 不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
    }
}

优化时间复杂度为O(N)，空间复杂度为O(1)

class Solution {
    public void nextPermutation(int[] nums) {
        // 1.从后向前获取逆序区域的前一位
        int index = findIndex(nums);
        // 判断数组是否处于最小组合状态
        if(index != 0){
            // 2.交换逆序区域刚好大于它的最小数字
            exchange(nums,index);
        }
        // 3.把原来的逆序区转为顺序
        reverse(nums,index);
    }
    
    public static int findIndex(int [] nums){
        for(int i = nums.length-1;i>0;i--){
            if(nums[i]>nums[i-1]){
                return i;
            }
        }
        return 0;
    }
    public static void exchange(int [] nums, int index){
        int head = nums[index-1];
        for(int i = nums.length-1;i>0;i--){
            if(head < nums[i]){
                nums[index-1] = nums[i];
                nums[i] = head;
                break;
            }
        }
    }
    public static void reverse(int [] nums, int index){
        for(int i = index,j = nums.length-1;i<j;i++,j--){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }   
}

Python

直接使用sorted()不符合题意

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)-1, -1, -1):
            for j in range(len(nums)-1, i, -1):
                if nums[j] > nums[i]:
                    nums[j], nums[i] = nums[i], nums[j]
                    nums[i+1:len(nums)] = sorted(nums[i+1:len(nums)])
                    return
        nums.sort()

另一种思路

class Solution:
    '''
    抛砖引玉：因题目要求“必须原地修改，只允许使用额外常数空间”，python内置sorted函数以及数组切片+sort()无法使用。  
    故选择另一种算法暂且提供一种python思路
    '''
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        for i in range(length-1, 0, -1):
            if nums[i-1] < nums[i]:
                for j in range(length-1, 0, -1):
                    if nums[j] > nums[i-1]:
                        nums[i-1], nums[j] = nums[j], nums[i-1]
                        break
                self.reverse(nums, i, length-1)
                break
            if n == 1:
                # 若正常结束循环，则对原数组直接翻转
                self.reverse(nums, 0, length-1)

    def reverse(self, nums: List[int], low: int, high: int) -> None:
        while low < high:
            nums[low], nums[high] = nums[high], nums[low]
            low += 1
            high -= 1

上一版本简化版

class Solution(object):
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n-2
        while i >= 0 and nums[i] >= nums[i+1]:
            i -= 1

        if i > -1: // i==-1,不存在下一个更大的排列
            j = n-1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
    
        start, end = i+1, n-1
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
        
        return nums

Go

//卡尔的解法
func nextPermutation(nums []int)  {
    for i:=len(nums)-1;i>=0;i--{
        for j:=len(nums)-1;j>i;j--{
            if nums[j]>nums[i]{
                //交换
                nums[j],nums[i]=nums[i],nums[j]
                reverse(nums,0+i+1,len(nums)-1)
                return 
            }
        }
    }
    reverse(nums,0,len(nums)-1)
}
//对目标切片指定区间的反转方法
func reverse(a []int,begin,end int){
    for i,j:=begin,end;i<j;i,j=i+1,j-1{
        a[i],a[j]=a[j],a[i]
    }
}

JavaScript

//卡尔的解法(吐槽一下JavaScript的sort和其他语言的不太一样，只想到了拷贝数组去排序再替换原数组来实现nums的[i + 1, nums.length)升序排序)
var nextPermutation = function(nums) {
    for(let i = nums.length - 1; i >= 0; i--){
        for(let j = nums.length - 1; j > i; j--){
            if(nums[j] > nums[i]){
                [nums[j],nums[i]] = [nums[i],nums[j]]; // 交换
                // 深拷贝[i + 1, nums.length)部分到新数组arr
                let arr = nums.slice(i+1);
                // arr升序排序
                arr.sort((a,b) => a - b);
                // arr替换nums的[i + 1, nums.length)部分
                nums.splice(i+1,nums.length - i, ...arr);
                return;
            }
        }
    }
    nums.sort((a,b) => a - b); // 不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
};

//另一种
var nextPermutation = function(nums) {
    let i = nums.length - 2;
    // 从右往左遍历拿到第一个左边小于右边的 i,此时 i 右边的数组是从右往左递增的
    while (i >= 0 && nums[i] >= nums[i+1]){
        i--;
    }
    if (i >= 0){
        let j = nums.length - 1;
        // 从右往左遍历拿到第一个大于nums[i]的数,因为之前nums[i]是第一个小于他右边的数，所以他的右边一定有大于他的数
        while (j >= 0 && nums[j] <= nums[i]){
            j--;
        }
        // 交换两个数
        [nums[j], nums[i]] = [nums[i], nums[j]];
   }
    // 对 i 右边的数进行交换
    // 因为 i 右边的数原来是从右往左递增的，把一个较小的值交换过来之后，仍然维持单调递增特性
    // 此时头尾交换并向中间逼近就能获得 i 右边序列的最小值
    let l = i + 1;
    let r = nums.length - 1;
    while (l < r){
        [nums[l], nums[r]] = [nums[r], nums[l]];
        l++;
        r--;
    }
};