31.下一个排列.md

31. 下一个排列

url

题目

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

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

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

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

方法

code

js

let nextPermutation = nums => {
    let reverse = (nums, i, j) => {
        while (i < j) {
            swap(nums, i++, j--);
        }
    };
    let swap = (nums, i, j) => {
        let t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    };
    let len = nums.length;
    if (len < 2)
        return;
    let i = len - 1;
    while (i > 0 && nums[i - 1] >= nums[i])
        i--;// 从后向前找第一个正序，这里最后i指向的是逆序起始位置
    reverse(nums, i, len - 1); // 翻转后面的逆序区域，使其变为正序
    if (i === 0)
        return;
    let j = i - 1;
    while (i < len && nums[j] >= nums[i])
        i++; // 找到第一个比nums[j]大的元素，交换即可
    // 交换
    swap(nums, i, j);
    return nums;
};

go

func nextPermutation(nums []int) {
	swap :=func (nums []int, i int, j int) {
		t := nums[i]
		nums[i] = nums[j]
		nums[j] = t
	}
	reverse := func (nums []int, i int, j int)  {
		for i < j {
			swap(nums, i, j)
			i++
			j--
		}
	}
	l := len(nums)
	if l < 2 {
		return
	}
	i := l - 1
	for i > 0 && nums[i-1] >= nums[i] {
		i-- // 从后向前找第一个正序，这里最后i指向的是逆序起始位置
	}
	reverse(nums, i, l - 1) // 翻转后面的逆序区域，使其变为正序
	if i == 0 {
		return
	}
	j := i - 1
	for i < l && nums[j] >= nums[i] {
		i++ // 找到第一个比nums[j]大的元素，交换即可
	}
	swap(nums, i, j)
}

java

class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        if (len < 2) return;
        int i = len - 1;
        while (i > 0 && nums[i - 1] >= nums[i])
            i--; // 从后向前找第一个正序，这里最后i指向的是逆序起始位置
        reverse(nums, i, len - 1); // 翻转后面的逆序区域，使其变为正序
        if (i == 0) return;
        int j = i - 1;
        while(i < len && nums[j] >= nums[i])
            i++; // 找到第一个比nums[j]大的元素，交换即可
        // 交换
        swap(nums, i, j);
    }
    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }
    private void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}