摘要：解題思路這道題是要將排列按字典序排列，然后求出下一個(gè)排列，一種辦法是我們先求出所有的排序情況，但是題目規(guī)定不能占有額外空間。每次求出一個(gè)數(shù)字后，要及時(shí)的把它從中刪除掉。采用來構(gòu)造結(jié)果序列。

Permutations
Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

1.解題思路

此題為求排列，與組合相比較，排列是順序相關(guān)的，但是已經(jīng)被選中的數(shù)字是不能再次出現(xiàn)的，所以我們想到維護(hù)一個(gè)isUsed[]數(shù)組來表示某個(gè)數(shù)字是否已被選中過。

2.代碼

public class Solution {
    List> res=new ArrayList>();
    public List> permute(int[] nums) {
        if(nums.length==0) return res;
        boolean[] isUsed=new boolean[nums.length];
        permuteHelper(nums,isUsed,nums.length,new ArrayList());
        return res;
    }
    private void permuteHelper(int[] nums, boolean[] isUsed,int count,List pre){
        if(count==0){
            res.add(pre);
            return;
        }
        for(int i=0;i cur=new ArrayList(pre);
                cur.add(nums[i]);
                isUsed[i]=true;
                permuteHelper(nums,isUsed,count-1,cur);
                isUsed[i]=false;
            }
        }
    }
}

Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

1.解題思路

包含重復(fù)的數(shù)字，所以我們要對(duì)重復(fù)的排列序列進(jìn)行排除，首先我們對(duì)數(shù)組進(jìn)行排序，然后當(dāng)發(fā)現(xiàn)某個(gè)數(shù)與前一個(gè)數(shù)相同時(shí)，就判斷前一個(gè)數(shù)是否被選中，如果未被選中，則排除掉當(dāng)前重復(fù)數(shù)，直接進(jìn)入下一個(gè)；因?yàn)槿绻耙粋€(gè)數(shù)已被選中，說明現(xiàn)在正處于前一個(gè)數(shù)的遞歸選數(shù)字過程中，則不能排除當(dāng)前重復(fù)數(shù)。

public class Solution {
    List> res=new ArrayList>();
    public List> permuteUnique(int[] nums) {
        if(nums.length==0) return res;
        Arrays.sort(nums);
        permuteUniqueHelper(nums,new boolean[nums.length],nums.length,new ArrayList());
        return res;
    }
    private void permuteUniqueHelper(int[] nums,boolean[] used,int count, List pre){
        if(count==0){
            res.add(pre);
            return;
        }
        for(int i=0;i0&&nums[i]==nums[i-1]&&!used[i-1]) continue;
            List cur=new ArrayList(pre);
            if(!used[i]){
                cur.add(nums[i]);
                used[i]=true;
                permuteUniqueHelper(nums,used,count-1,cur);
                used[i]=false;
            }
        }
    }
}

Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

1.解題思路

這道題是要將排列按字典序排列，然后求出下一個(gè)排列，一種辦法是我們先求出所有的排序情況，但是題目規(guī)定不能占有額外空間。根據(jù)example， 我們發(fā)現(xiàn)其實(shí)我們可以從數(shù)組后面開始比較相鄰的兩個(gè)數(shù)，如果后面的數(shù)小于前面的數(shù)，則繼續(xù)往前；如果后面的數(shù)大于前面的數(shù)，將前面那個(gè)數(shù)下標(biāo)標(biāo)記為i-1，則我們知道i-1這個(gè)數(shù)的位置是需要交換，那和后面的哪個(gè)交換呢？肯定是和從i開始往后找比i-1數(shù)大，但是又是后面最小的數(shù)作交換。
這樣i-1這個(gè)位置的數(shù)就確定下來了。因?yàn)閯偛盼覀円宦飞蠑?shù)組末尾往前，經(jīng)過的數(shù)字都是逆序的，我們現(xiàn)在要做的就是反轉(zhuǎn)這些數(shù)，這樣就得到了next permutation.

public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length==0) return;
        int i=nums.length-1;
        for(;i>0;i--){
            if(nums[i]>nums[i-1]) break;
            
        }
        if(i==0) {
            reverse(nums,0,nums.length-1);
            return;
        }
        int first=i-1; //the first num need to be swapped.
        int nextbig=nums[i];
        int nextbig_index=i;
        for(int j=i+1;j=nums[j]&&nums[j]>nums[first]){
                nextbig=nums[j];
                nextbig_index=j;
            }
        }
        swap(nums,first,nextbig_index);
        reverse(nums,first+1,nums.length-1);
    }
    private void reverse(int[] nums, int start,int end){
        while(start
Permutation Sequence
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
1.解題思路
這個(gè)題目其實(shí)涉及到一些數(shù)學(xué)規(guī)律，我們仔細(xì)看例子會(huì)發(fā)現(xiàn)其實(shí)以每個(gè)數(shù)字開頭的序列都會(huì)有(n-1)!個(gè)，所以我們只要用k/(n-1)!就可以得到第一個(gè)數(shù)字,在求出第一個(gè)數(shù)字后，我們只要將k%(n-1)!，就可以繼續(xù)循環(huán)求第二個(gè)數(shù)。
需要注意的地方有：
1）代碼里我們是把數(shù)字放入了一個(gè)List中，而list的下標(biāo)是以0開始的，所以我們首先將k-1。
2）每次求出一個(gè)數(shù)字后，要及時(shí)的把它從List中刪除掉。
3）采用StringBuilder來構(gòu)造結(jié)果序列。
2.代碼
public class Solution {
    public String getPermutation(int n, int k) {
        List nums=new ArrayList();
        int factorial=1;
        int i=1;
        while(i<=n){
            factorial*=i;
            nums.add(i);
            i++;
        }
        k--; 
        int j=n;
        StringBuilder sb=new StringBuilder();
        while(nums.size()>0){
            factorial=factorial/j;
            int index=k/factorial;
            sb.append(nums.get(index));
            nums.remove(index);
            j--;
            k=k%factorial;
        }
        
        return sb.toString();
    }
}