下一个排列
实现获取下一个排列的函数, 算法需要将给定数字序列重新排列成字典序中下一个更大的排列.
如果不存在下一个更大的排列, 则将数字重新排列成最小的排列 (即升序排列).
必须原地修改, 只允许使用额外常数空间.
以下是一些例子, 输入位于左侧列, 其相应输出位于右侧列.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
思路: 首先观察一个数组 1 2 7 4 3 1 .
他的下一个排列是 1 3 1 2 4 7 .
列举多个这样的数组可以发现规律,
原始数组在从右往左遍历, 2,7 为 降序排列, 在遍历 1,3,4,7 时都为升序, 则找到如下规律:
当遍历发现为降序排列: 即 nums[i]>nums[i-1]. 我们依然从右往左遍历寻找 1,2,4,7 中第一个比 2 更大的
数字.
之后交换 2 ,3 . 因此 数组变为 1 3 7 4 2 1 可以发现 3 之后的数组 7 4 2 1 从左往右是整齐的降序排列.
因此对其进行逆转. 代码如下:
JAVA:
- class Solution {
- public void nextPermutation(int[] nums) {
- int len=nums.length;
- int i,j; // 提前获得下标用于后面的 swap 交换
- for(i=len-2;i>=0;i--){ // 这里用 len-2, 避免了用 Len-1 之后使用 nums[i-1] 的尴尬 . 或者 for(i=nums.size()-1;i>0;i--) 用 nums[i]>nums[i-1]
- if(nums[i+1]>nums[i]){
- for(j=len-1;j>i;j--){ // 寻找后面序列总第一个比 nums[i] 大的数字
- if(nums[j]>nums[i])break;
- }
- int temp=nums[i]; // 找到第一个比 Nums[i] 更大的数, 两者交换之后依然是一个整齐的降序数组, 因此将其反转
- nums[i]=nums[j];
- nums[j]=temp;
- reverse(nums,i+1,len-1);
- return;
- }
- }
- reverse(nums,0,len-1);
- }
- public void reverse(int[] nums,int left,int right){
- while(left<right){
- int temp=nums[left];
- nums[left]=nums[right];
- nums[right]=temp;
- left++;right--;
- }
- }
- }
C++:
- class Solution {
- public:
- void reverse1(vector<int>& nums,int l,int r){
- while(l<r){
- int temp=nums[l];
- nums[l]=nums[r];
- nums[r]=temp;
- l++,r--;
- }
- }
- void nextPermutation(vector<int>& nums) {
- int j;
- for(int i=nums.size()-1;i>0;i--){
- if(nums[i]>nums[i-1]){
- for( j=nums.size()-1;j>i;j--){
- if(nums[j]>nums[i-1]){
- break;
- }
- }
- swap(nums[i-1],nums[j]);
- reverse1(nums,i,nums.size()-1);
- return;
- }
- }
- reverse(nums.begin(),nums.end());
- }
- };
来源: http://www.bubuko.com/infodetail-2794094.html