LeetCode Permutation Sequence

Permutation Sequence

The set[1,2,3,…,n]contains a total ofn! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, forn= 3):

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

Givennandk, return thekthpermutation sequence.

Note:Givennwill be between 1 and 9 inclusive.

本题最直接的算法就是，一个一个permutation的产生，然后数到k就是答案了，但是这样的程序很慢，高手是不能这样写程序的。O(∩_∩)O~

其实这类题有个很特别的方法做的，不过没看过的话，就很难想出来了。

可以参考下面博客，求一个数列的全部全排列。而不同的就是这里只是求某个特定的全排列。

http://blog.csdn.net/kenden23/article/details/17166105

使用上面博客中的最后一个方法，定位下标的方法就可以写出很快的程序了。

下面程序8ms都可以过，我分了几个函数，希望可以清晰一点吧。

class Solution {
public:
    string getPermutation(int n, int k) {
		vector<int> bound = generatBound(n);
		vector<int> table = converNumToTable(bound, n, k);
		return permuteK(n, k, bound, table);
	}

	string permuteK(int n, int k, vector<int> &bound, vector<int> &table)
	{
		vector<int> num(n);
		string res;
		for (int i = 1; i <= n; i++)
		{
			num[i-1] = i;
		}

		for (int j = 0; j < n; j++)
		{
			res.push_back(num[table[j]] + '0');
			num.erase(num.begin()+table[j]);
		}

		return res;
	}

	vector<int> converNumToTable(vector<int> &bound, int n, int num)
	{
		vector<int> table(n);
		num--;
		for (int i = n-2; i>=0 && num > 0; i--)
		{
			table[i] = num % (bound[i]+1);
			num /= (bound[i]+1);
		}
		return table;
	}

	vector<int> generatBound(int n)
	{
		vector<int> bound(n);
		for (int i = 0; i < n; i++)
		{
			bound[i] = n-1-i;
		}
		return bound;
	}
};

//2014-1-29 update
	vector<int> table;

	string getPermutation(int n, int k) 
	{
		convertToTable(n, k-1);
		string s, rs;
		for (int i = 1; i <= n; i++)
		{
			s.push_back(i+'0');
		}

		for (int i = 0; i < n; i++)
		{
			rs.push_back(s[table[i]]);
			s.erase(s.begin()+table[i]);
		}
		return rs;
	}
	
	void convertToTable(int n, int k)
	{
		table.clear();
		table.resize(n);

		for (int i = n - 2, j = 2; i >= 0 && k > 0; i--, j++)
		{
			table[i] = k%j;
			k /= j;
		}
	}