Leetcode#31. Next Permutation（java）

本文主要是介绍Leetcode#31. Next Permutation（java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目含义：给定一个int数组，输出其全排列中的下一个序列。例如：输入数组：2431，显然其全排列有：{1234,1243,1324,1342,2134,2143,2314,2341,2413,2431,3124，...},即所有数字从小到大依次排列，则序列2431的下一个序列为3124。我们的目的就是找出给定数组的下一个序列。

2. 解题思路：分三步：

step1：从后往前找第一个不再升序排列的元素i，比如2431 第一个不再升序的元素i=2。

step2：从后往前找到第一个大于i的元素j，交换i和j，比如2431，第一个大于2的元素是3，将2和3交换后数组为3421。

step3: 将找到的第一个不再升序的元素i所在位置后面的所有元素逆序。例子中，元素i=2后面的元素是421，逆序后为124，则整个数组变为3124，恰好是全排

序后2431的下一个序列。

我们试着理解一下，找到的元素i恰巧是我们需要变动的第一个元素，比如2431，需要变动的第一个元素是2，那变为什么呢？变为下一个比它大的元素中最小的元素，

例子中是3。因此将2和3交换。再看为什么要将i所在的位置后面的所有元素逆序呢？我们回顾一下元素i是怎么找到的呢？是第一个不再升序的元素，也就是说元素i后面的所有元素都是升序排列的，因为全排序时数字是从小到达排列的，因此紧挨着的下一个序列肯定是较小的元素排在前面，所以需要将421这样的元素都逆序为124这样的。

3. 边界条件：当我们找不到第一个不再升序排列的元素时，将整个数组逆序输出。

4.代码实现：

public class Solution {
    public void nextPermutation(int[] nums) {
   int temp = nums[nums.length-1];
   int i=nums.length-2;
   int j=nums.length-1;
   for(;i>=0;--i){
       if(nums[i]<temp) break;
       temp = nums[i];
   }
   if(i<0){// //当元素中找不到破坏升序的，也就是整个序列都是降序排列，比如654321，比如111，等。。。将元素逆序输出
       Arrays.sort(nums, 0, nums.length);
   }
   else{
       for(;j>=0;--j){
           if(nums[j]>nums[i]) break;

       }
       if(j<0) {//System.out.println("在第二阶段没找到比第一阶段元素nums[i]"+nums[i]+"大的元素");
       System.exit(1);}
       //switch
       temp = nums[i];
       nums[i]=nums[j];
       nums[j]=temp;
       //switch

       Arrays.sort(nums, i+1, nums.length);
       }
   return;
    }

}

5. 运行结果。