lintcode190. 下一个排列

刺骨的言语ヽ痛彻心扉 2023-07-07 05:48 13阅读 0赞

给定一个若干整数的排列，给出按正数大小进行字典序从小到大排序后的下一个排列。  
如果没有下一个排列，则输出字典序最小的序列。

样例
    样例 1:
    
    输入:1,2,3
    输出:1,3,2
    样例 2:
    
    输入:3,2,1
    输出:1,2,3
    样例 3:
    
    输入:1,1,5
    输出:1,5,1
    挑战
    不允许使用额外的空间。

1、是从后往前找，找到第一个降序的数字，因为如果一直都是升序的话，说明一部分应该是全排列的最大情况。第一个比它后一个数小的数，就是需要替换为比它大一点的那个数，即3。  
2、找到3以后，需要把它替换成一个比它大一点的数，于是再从后往前找，找到第一个比它大的数，在上面的例子，就是4.  
3、将3和4交换，由于后半部分已经是最大的全排列，逆序一下得到最小的全排列。  
4、若数组本身就是最大全排列，直接逆序整个数组即可。  
5、若数组长度小于1，则直接返回即可。

class Solution {
        
    public:
        /**
         * @param nums: An array of integers
         * @return: nothing
         */
        void nextPermutation(vector<int> &nums) {
        
            // write your code here
            int len=nums.size();
            if(len==0) return;
            int index=len-1;
            for (int i = len-2; i >= 0; i--) {
        
                if(nums[i]<nums[i+1])
                {
        
                    index=i;
                    break;
                }
            }
            if(index==len-1)
            {
        
                reverse(nums.begin(),nums.end());
                return ;
            }
            for (int i = len-1; i > index ; i--) {
        
                if(nums[i]>nums[index])
                {
        
                    swap(nums[i],nums[index]);
                    break;
                }
            }
            reverse(nums.begin()+index+1,nums.end());
        }
    };