題目描述

實現(xiàn)函數(shù)next permutation（下一個排列）：將排列中的數(shù)字重新排列成字典序中的下一個更大的排列。將排列中的數(shù)字重新排列成字典序中的下一個更大的排列。
如果不存在這樣的排列，則將其排列為字典序最小的排列（升序排列）
需要使用原地算法來解決這個問題，不能申請額外的內(nèi)存空間
下面有機組樣例，左邊是輸入的數(shù)據(jù)，右邊是輸出的答案
1,2,3→1,3,2
3,2,1→1,2,3
1,1,5→1,5,1

分析

• 先從末尾向前找出 第一個非升序（這個升序是不嚴格升序）的下標，如 1 2 6642
  先找出來標出的2，由于2 后面的數(shù)字全是降序，這是后面四位數(shù)所能組成的最大數(shù)。
• 如果想讓整體變大，而且是變大成相鄰的數(shù)字，可以考慮將 2變大一些，因為后面四位數(shù)是他們所能組成的最大數(shù)了，要想變大，用6642里面比2稍微大一些的數(shù)替換2，就可以使整體變大一些。
• 剩下的四位數(shù)要盡可能小，于是將他們升序排列
• 特殊情況，可能所給的數(shù)字是降序的 54321，則直接將其排序。

java 代碼

import java.util.*;
public class Solution {
    public void nextPermutation(int[] num) {
        if(num == null || num.length == 0){return ;}
        
        int last = num.length - 2;
        while(last >=0 && num[last] >= num[last + 1]){
            last--;
        }
        if(last < 0){
            Arrays.sort(num);
            return;
        }
        int i = last + 1;
        while(i < num.length && num[i] > num[last]){
            i++;
        }
        int temp = num[last];
        num[last] = num[i-1];
        num[i-1] = temp;
        //swap(last,i-1);
        //sort(last+1,num.length -1);
        Arrays.sort(num,last + 1,num.length);
    }
}