LeetCode-31 下一个排列

用户3470542

发布于 2019-06-26 16:19:59

66500

文章被收录于专栏：算法半岛算法半岛

运行总次数：0

> 题目：31. 下一个排列

> 难度：中等

> 分类：数组

> 解决方案：数组遍历

今天我们学习第31题下一个排列，这是一个中等的数组题。我们先看看这道题的题目描述。

题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。

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

1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1

分析

这是一个数组排列的题，首先我们需要弄明白什么是数组的下一个排列。我们可以对数字1、2和3这三个数形成的数组进行排列，如下图所示：

对具体排列方法分析如下图所示：

上述分析所对应的 java代码如下所示：

class Solution {    public void nextPermutation(int[] nums) {        // 从右向左遍历，存储第一个下降的数的坐标        int i = 0;        // 从右向左遍历，存储第一个大于nums[i]的数的坐标        int j = 0;
        if(nums == null || nums.length < 2)            return ;
        // 从右向左找到第一个降序的数，坐标为i        for(int k=nums.length -2; k>=0; k--){            if(nums[k] < nums[k+1]){                i = k;                break;            }        }
        // 从右向左找到第一个大于nums[i]的数，坐标为j        for(int k=nums.length-1; k>=0; k--){            if(nums[k] > nums[i]){                j = k;                break;            }        }
        // 交换 nums[i] 和 nums[j]        swap(nums, i, j);
        // 转置从i+1(0)到nums.length-1的数         int n = 0;        if(i == 0 && j == 0)            n = 0;        else             n = i + 1;        int m = nums.length-1;        while(n < m){            swap(nums, n, m);            ++n;            --m;        }    }
    // 数组中两个数字交换函数    private void swap(int[] nums, int i, int j){        int tmp = nums[i];        nums[i] = nums[j];        nums[j] = tmp;    }}