题目位置

1.思路

以5,2,4,3,1为例,要变到下一个的话,首先先判断当前是不是存在下一个,判断的依据是任何一位上的数字是否都比后一个数字大,也就是倒序,此例中2后面存在比2大的数,所以先步骤为:

• 后面比2大但是最小的数字==,也就是3,虽然4也比2大,但是不是下一个数字
• 交换2,3的位置变成 5,3,4,2,1,这个比原数字大,但是不是下一个,紧接着将3后面的数字变成最小的就行了,也就是5,3,1,2,4

对于第一种情况,a[i]和后面的数字a[j],a[j]满足j属于[i+1,length-1]之间且a[i]<a[j],a[j]是[i+1,length-1]之间满足条件最小的,交换a[i],a[j],然后将[i+1,length-1]之间进行升序排序.
例如:5,2,4,3,1
1.首先找到2也就是a[1]小于后面的数字.然后找到后面比a[1]大且最小的数字3,交换2,3为5,3,4,2,1
2.然后将后面的[4,2,1]进行排序即可变成5,3,1,2,4
对于第二种情况,例如5,4,3,2,1排序为1,2,3,4,5

2.代码

 public void nextPermutation(int[] nums) {
        for(int i=nums.length-1;i>0;i--){
            if(nums[i]>nums[i-1]){
               int temp = nums[i],tempIndex = i;
               for(int j = nums.length;j>i;j++){
                   if(nums[j]>nums[i-1]&&nums[j]<temp){
                       temp = nums[j];
                       tempIndex = j;
                   }
               }
               swap(i-1,tempIndex,nums);
               Arrays.sort(nums,i,nums.length);
               return;
            }
        }
        Arrays.sort(nums);

    }
    private void swap(int i, int i1, int[] num) {
        int temp = num[i];
        num[i]=num[i1];
        num[i1]=temp;
    }