31. 下一个排列

叁歲伎倆 2022-09-09 09:15 141阅读 0赞

[https://leetcode-cn.com/problems/next-permutation/][https_leetcode-cn.com_problems_next-permutation]

难度中等1297收藏分享切换为英文接收动态反馈

实现获取 **下一个排列** 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。

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

必须**[ 原地 ][Link 1]**修改，只允许使用额外常数空间。

**示例 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]

**提示：**

*  `1 <= nums.length <= 100`
 *  `0 <= nums[i] <= 100`

通过次数204,067提交次数546,709

class Solution {
        public void nextPermutation(int[] nums) {
            int index = 0;
            for(int i=nums.length-1;i>0;i--)
            {
                if(nums[i-1]<nums[i])
                {
                    for(int j=nums.length-1;j>i-1;j--)
                    {
                        
                        if(nums[i-1]<nums[j])
                        {
                            int temp = nums[i-1];
                            nums[i-1] = nums[j];
                            nums[j] = temp;
                            index=i;
                            break;
                        }  
                    }
                    break;
                }
            }
            Arrays.sort(nums,index,nums.length);
        }
    }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_19_color_FFFFFF_t_70_g_se_x_16][]

[https_leetcode-cn.com_problems_next-permutation]: https://leetcode-cn.com/problems/next-permutation/
[Link 1]: https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/2ed710eecc5b48dfb36bf9cbbd557480.png