31、下一个排列

leetcode

Created At : 2020-07-26 00:19

Count:323 Views 👀 :

Comment:

31、下一个排列
题解
1. 1、

31、下一个排列

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

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

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题解

1、

从小到大，从后往前
代码

// java
class Solution {
    // 反转start之后的元素
    private void reverse(int[] nums,int start) {
        int i = start,j = nums.length - 1;
        while(i < j) {
            nums[i] = nums[i]^nums[j];
            nums[j] = nums[j]^nums[i];
            nums[i] = nums[j]^nums[i];
            
            i++;
            j--;
        }
    }
    public void nextPermutation(int[] nums) {
        // 遍历到第一个递减点
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {// 找到第一个递减元素
            i--;
        }
        if (i >= 0) {// 不是最后第一个元素，数组非递增
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {// 找到第一大于目标值的元素
                j--;
            }
            nums[i] = nums[i]^nums[j];
            nums[j] = nums[j]^nums[i];
            nums[i] = nums[j]^nums[i];
        }
        reverse(nums,i + 1);
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com