60. 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 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.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

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

Example 2:

Input: n = 4, k = 9
Output: "2314"

---

求1~n的所有排列中，第k大的数。肯定不可能先用LeetCode Permutations把所有排列找出来，然后sort取第k个，肯定TLE，所以换思路。

假设给的例子中，原数组为s=”123″，要求第5大的数，即”312″。我们首先找出这个数的首位数字是什么。我们知道以某个数字固定开头的排列个数=(n-1)!=2!=2，即以1和2开头的排列数共有2*2=4个，而我们要求的是第5大的数，所以这个数开头必须是3=5/2+1=ceil( k / (n-1)! )=m。
确定了第一位之后，把3从原数组s中删掉，然后递归查找剩余数组s=”12″中第5-2*2=1=k-(m-1)*(n-1)!位的排列。显然就是最小的“12”了，然后拼起来为”312″。

完整代码如下：

class Solution {
public:
    vector<int> fact(int n)
    {
        vector<int> vFact;
        vFact.push_back(1); // 0!=1
        int ans = 1;
        for (int i = 1; i <= n; i++) {
            ans *= i;
            vFact.push_back(ans);
        }
        return vFact;
    }
    char work(string& candidates, vector<int>& vFact, int& k)
    {
        int tmp = vFact[candidates.size() – 1];
        int idx = ceil(k / float(tmp));
        idx–;
        char ans = candidates[idx];
        candidates.erase(idx, 1);
        k -= idx * tmp;
        return ans;
    }
    string getPermutation(int n, int k)
    {
        vector<int> vFact = fact(n);
        string candidates = string("123456789").substr(0, n);
        string ans(n, ‘ ‘);
        for (int i = 0; i < n; i++)
            ans[i] = work(candidates, vFact, k);
        return ans;
    }
};

本代码提交AC，用时0MS。

二刷。直接DFS的过程就是从小到大排序的过程，DFS到第k个排列的时候返回即可：

class Solution {
public:
	void dfs(string &s, int n, vector<int>& visited, int k, int &m, string &ans) {
		if (m == k)return;

		if (s.size() == n) {
			++m;
			if (m == k)
				ans = s;
			return;
		}
		for (int i = 1; i <= n; ++i) {
			if (visited[i] == 0) {
				s.push_back('0' + i);
				visited[i] = 1;
				dfs(s, n, visited, k, m, ans);
				s.pop_back();
				visited[i] = 0;
			}
		}
	}
	string getPermutation(int n, int k) {
		string s = "", ans = "";
		vector<int> visited(n + 1, 0);
		int m = 0;
		dfs(s, n, visited, k, m, ans);
		return ans;
	}
};

本代码提交AC，用时1356MS，太慢了，还是用之前的方法吧。