LeetCode Permutation Sequence

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

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

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.


求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。

Leave a Reply

Your email address will not be published. Required fields are marked *