leetcode31. 下一个排列

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

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

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

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

思路：贪心的想法，想找到最小的，比这个排列大，的排列：

第一，我们希望第一个变大的数字X尽可能地向后，因为X越向后，生成的排列更小。

如何做到这一点？从前往后找到第一个nums[i]<nums[i+1]的数字，如54321就没有这种数字，所以也没有更大的序列，如45321，4就是第一个。

第二：我们希望这个X被替换的尽可能地小，如1254321，我们要替换2，我们应该找3来替换。

第三：我们希望X之后的数字是递增的，这样才能保证是最小排列，如1254321，我们替换为1354221之后，要把54221这部分逆置。

  

   

    

     

    
    

     

      public class Solution {
     
    
   

    

     

    
    

     
 public void nextPermutation(int[] nums) {
     
    
   

    

     

    
    

     
 int i = nums.length - 2;
     
    
   

    

     

    
    

     
 while (i >= 0 && nums[i + 1] <= nums[i]) {
     
    
   

    

     

    
    

     

       i--;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if (i >= 0) {
     
    
   

    

     

    
    

     
 int j = nums.length - 1;
     
    
   

    

     

    
    

     
 //找到最小的大于nums[i]的值
     
    
   

    

     

    
    

     
 while (j >= 0 && nums[j] <= nums[i]) {
     
    
   

    

     

    
    

     

       j--;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 //交换nums[i]和nums[j]
     
    
   

    

     

    
    

     
 int temp = nums[i];
     
    
   

    

     

    
    

     

       nums[i] = nums[j];
     
    
   

    

     

    
    

     

       nums[j] = temp;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 //把后面的序列反转成递增的
     
    
   

    

     

    
    

     

       i++;
     
    
   

    

     

    
    

     
 int j=nums.length - 1;
     
    
   

    

     

    
    

     
 while (i < j) {
     
    
   

    

     

    
    

     
 int temp = nums[i];
     
    
   

    

     

    
    

     

       nums[i] = nums[j];
     
    
   

    

     

    
    

     

       nums[j] = temp;
     
    
   

    

     

    
    

     

       i++;
     
    
   

    

     

    
    

     

       j--;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104360900