leetcode:31.下一个排列

小咪咪 2022-02-20 16:24 180阅读 0赞

### 题目描述： ###

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

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

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。  
`1,2,3`→ `1,3,2`  
`3,2,1`→ `1,2,3`  
`1,1,5`→ `1,5,1`

##### 题目难度：中等 #####

##### 分析： #####

题目的下一个排列可以理解为：把数组看成一个int值，找出下一个比当前更大的int值，当然元素不能变，只能交换。所以只有降序排列的数组是没有下一个排列的。那么我们只要从后往前，找到第一个后元素大于前元素的位置，记录前元素为`index`，说明此数组不是降序排序，找到之后再从后往前遍历，找到第一个大于index索引的值，并且交换即可，这里只需要遍历到index后一位。  
代码如下：

class Solution { 
        public void nextPermutation(int[] nums) { 
        	// 如果数组的长度等于1，就不需要排列了，直接返回
            int l = nums.length;
            if (l == 1) { 
                return;
            }
            // 定义一个索引，并且从后往前找到第一个nums[i] > nums[i - 1]的位置
            int index = -1;
            for (int i = l - 1; i > 0; i--) { 
                if (nums[i] > nums[i - 1]) { 
                    index = i - 1;
                    break;
                }
            }
            // 如果没有找到，说明数组是降序排列，没有下一个排列，直接升序排序即可
            if (index == -1) { 
                Arrays.sort(nums);
                return;
            }
            // 继续从后向前遍历，找到第一个比index索引的值大的值
            for (int i = l - 1; i > index; i--) { 
                if (nums[i] > nums[index]) { 
                    // 交换位置 nums[index] 和 nums[i]交换
                    swap(nums, index, i);
                    break;
                }
            }
            // 对index后面的元素首尾交换，因为这个地方肯定是倒序排序的
            int i = index + 1, j = l - 1;
            while (i < j) { 
                swap(nums, i, j);
                i++;
                j--;
            }
        }
        // 用来交换数组元素的方法
        private void swap(int[] nums, int i, int j) { 
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

这里借用官方的动图来让大家理解更深刻：  
![交换过程][31_Next_Permutation.gif]

##### 总结： #####

时间复杂度为 O ( n ) O(n) O(n)，需要遍历数组，最差需要遍历两次全数组。

[31_Next_Permutation.gif]: https://leetcode-cn.com/media/original_images/31/31_Next_Permutation.gif