LeetCode

题目：

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):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.

思路：

除法和求余运算，对每一组数往下递推

package permutation;

import java.util.ArrayList;
import java.util.List;

public class PermutationSequence {

    public String getPermutation(int n, int k) {
        List<Integer> l = new ArrayList<Integer>();
        for (int i = 1; i <= n; ++i) 
            l.add(i);
        --k;
        StringBuilder sb = new StringBuilder();
        for (int i = n; i > 0; --i) {
            int fib = fib(i - 1);
            int index = k / fib;
            k = k % fib;
            sb.append((char)('0' + l.get(index)));
            l.remove(index);
        }
        return sb.toString();
    }
    
    private int fib(int n) {
        int res = 1;
        for (int i = 1; i <= n; ++i)
            res *= i;
        return res;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        PermutationSequence p = new PermutationSequence();
        System.out.println(p.getPermutation(4, 5));
    }

}