求一個(gè)數(shù)組的全排列锭环。

遇到的問題：

1.忘記了字典序排列的定義聪全；
2.思考時(shí)間過長；
3.沒有及時(shí)找到全排列和字典序之間的關(guān)系辅辩；

想到的解題思路：

1.用字典序找到下一個(gè)排序难礼；
2.全排序共有n!種組合，找夠停止循環(huán)玫锋；

代碼如下：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
// 如果數(shù)組長度是零直接返回
        if(nums.length == 0)
            return ans;
//求數(shù)組全排列
        int n = nums.length;
        int sum = 1;
        for(int i=2;i<=n;i++)
            sum *=i;
        for(;sum>0;sum--){
            ans.add(nextPermutation(nums));
        }
        return ans;
    }
//按照字典序求下一個(gè)排列
    public List<Integer> nextPermutation(int[] nums){
        int flag = 0;
        int j = 0;
//從頭開始找到比右邊數(shù)字的小的數(shù)的最大序號j
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]<nums[i+1]){
                flag = i;
                if(flag > j)
                    j = flag;
            }
        }
        List<Integer> l = new ArrayList<>();
        int k = 0;
//從j開始蛾茉，找到比j大的最小的數(shù)的序號k
        for(int i=j+1;i<nums.length;i++){
            if(nums[i]>nums[j])
                k = i;
            else
                break;
            }
        if(k == 0)
            Arrays.sort(nums);
        else{
//交換j，k
            int tmp = nums[j];
            nums[j] = nums[k];
            nums[k] = tmp;
//倒置j+1到n-1之間的數(shù)得到字典序的下一個(gè)排列
            for(int i=1;i<=(nums.length-j-1)/2;i++){
                tmp = nums[nums.length-i];
                nums[nums.length-i] = nums[j+i];
                nums[j+i] = tmp;
            }
        }
        for(int i=0;i<nums.length;i++)
            l.add(nums[i]);
        return l;
    }
}

附加內(nèi)容：

1.字典序的概念：

設(shè)P是1～n的一個(gè)全排列

1）從排列的右端開始撩鹿，找出第一個(gè)比右邊數(shù)字小的數(shù)字的序號j（j從左端開始計(jì)算）谦炬，即 j=max{i|p_i<p_i+1}

2）在p_j的右邊的數(shù)字中，找出所有比p_j大的數(shù)中最小的數(shù)字p_k节沦，即 k=max{i|p_i>p_j}（右邊的數(shù)從右至左是遞增的键思，因此k是所有大于p_j的數(shù)字中序號最大者）

3）對換p_j，p_k

4）再將p_j+1......p_k-1p_kp_k+1......p_n倒轉(zhuǎn)得到排列p'=p₁p₂.....p_j-1p_jp_n.....p_k+1p_kp_k-1.....p_j+1甫贯，這就是排列p的下一個(gè)排列吼鳞。

2.全排列概念：

從n個(gè)不同元素中任取m（m≤n）個(gè)元素，按照一定的順序排列起來叫搁，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列常熙。
公式：全排列數(shù)f(n)=n!(定義0!=1)