力扣(LeetCode)31

系统管理员 2022-03-07 14:00 170阅读 0赞

题目地址：  
[https://leetcode-cn.com/probl...][https_leetcode-cn.com_probl...]

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

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

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

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

解答：  
直接给出步骤：  
1从右到左扫描数组找出第一个升序对(nums\[j-1\],nums\[j\])  
2从右到左扫描数组找出第一个大于nums\[j-1\]的数nums\[k\]  
3交换nums\[j-1\],nums\[k\]  
4对num\[j...nums.length-1\]转置。

java ac代码:

class Solution {
        public void nextPermutation(int[] nums) {
            boolean flag = true;
            int i = 0;
            for(;i < nums.length-1;i++)
                if(nums[i] < nums[i+1])
                {
                    flag = false;
                    break;
                }
            if(flag)
            {
                int x = 0,y = nums.length-1;
                while(x < y)
                {
                    swap(nums,x,y);
                    x++;
                    y--;
                }
            }
            else
            {
                i = nums.length-1;
                while(i >= 1)
                    if(nums[i] <= nums[i-1])i--;
                else break;
                int j = nums.length-1;
                for(;j >= 0;j--)
                    if(nums[j] > nums[i-1])break;
                swap(nums,i-1,j);
                int x = i,y = nums.length-1;
                while(x < y)
                {
                    swap(nums,x,y);
                    x++;
                    y--;
                }
            }
            
            
        }
        
        void swap(int[] nums,int x,int y)
        {
              int temp = nums[x];
              nums[x] = nums[y];
              nums[y] = temp;
            
        }
    }

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