題目位置

1.思路

以5,2,4,3,1為例,要變到下一個(gè)的話,首先先判斷當(dāng)前是不是存在下一個(gè),判斷的依據(jù)是任何一位上的數(shù)字是否都比后一個(gè)數(shù)字大,也就是倒序,此例中2后面存在比2大的數(shù),所以先步驟為:

• 后面比2大但是最小的數(shù)字==,也就是3,雖然4也比2大,但是不是下一個(gè)數(shù)字
• 交換2,3的位置變成 5,3,4,2,1,這個(gè)比原數(shù)字大,但是不是下一個(gè),緊接著將3后面的數(shù)字變成最小的就行了,也就是5,3,1,2,4

對(duì)于第一種情況,a[i]和后面的數(shù)字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]之間進(jìn)行升序排序.
例如:5,2,4,3,1
1.首先找到2也就是a[1]小于后面的數(shù)字.然后找到后面比a[1]大且最小的數(shù)字3,交換2,3為5,3,4,2,1
2.然后將后面的[4,2,1]進(jìn)行排序即可變成5,3,1,2,4
對(duì)于第二種情況,例如5,4,3,2,1排序?yàn)?,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;
    }