060.PermutationSequence.md

60.Permutation Sequence

Question:

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 for n = 3:

"123"

"132"

"213"

"231"

"312"

"321"

Given n and k, return the kth permutation sequence.

Example:

Input: n = 3, k = 3
Output: "213"

Analysis:

给定ｎ个数字让求第k个序列．ｎ个数字总共的全排列最多有n!个，并且全排列有个规律．

给定一个n，以１开头的排列有(n-1)!个，同样对２和３也是，所以如果k小于等于(n-1)!，那么首位必为１，因为以１开头的全排列有(n-1)!个．

同样如果k大于(n-1)!，那么第一个数就应该为(k-1)/(n-1)!+1.这样找到了首位数字应该是哪个，剩下了(n-1)个数字，我们只需要重复上面的步骤，不断缩小k即可。

Solution:C++

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> sum(n,1), index(n,1);
        string result;
        for (int i = 1; i < n; i++){
            sum[i] = sum[i-1] * i;
            index[i] = i + 1;
        }
        //算出了阶乘以后
        //index是1,2,3,...,n
        k--; 
        for (int i = n - 1 ; i >= 0; i--)
        {
            int pos = k / sum[i];
            result += to_string(index[pos]); // 找出第几位.
            index.erase(index.begin() + pos); // 得把那一位去掉
            k = k % sum[i]; // 
        }
        return result;
    }
};

本题关键：

整除迭代，数学方法