首页 > 代码库 > 【leetcode】 Permutation Sequence

【leetcode】 Permutation Sequence

2024-07-06 18:41:08   228人阅读

问题：

对于给定序列1...n，permutations共有 n！个，那么任意给定k，返回第k个permutation。0 < n < 10。

分析：

这个问题要是从最小开始直接到k，估计会超时，受10进制转换为二进制的启发，对于排列，比如 1,2,3 是第一个，那么3！= 6，所以第6个就是3,2,1。也就是说，从开始的最小的序列开始，到最大的序列，就是序列个数的阶乘数。那么在1，3 , 2的时候呢？调整一下，变成2,1,3，就可以继续。

实现：

int getFactorial(int n)
{
	int factorial[10] = {-1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
	return factorial[n];
}
int checkFactorial(int n){
	// n is small, use liner search.
	int factorial[10] = {-1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
	for (int i = 1; i < 10; ++i)
	{
		if(n >= factorial[i] && n < factorial[i + 1])
			return i;
	}
	return 0;
}
void nextPermutetion(string &num)
{
	int i = num.size() - 1;
	while (i >= 1)
	{
		if(num[i] > num[i - 1])
		{
			--i;
			int ii = num.size() - 1;
			while (ii > i && num[ii] <= num[i]) --ii;
			if(ii > i)
			{
				swap(num[i], num[ii]);
				reverse(num.begin() + i + 1, num.end());
				break;
			}
		}
		else
			--i;
	}
}
string getPermutation(int n, int k) {

	if(k > getFactorial(n))
		return "";
	if(k <= 0 || 0 > n || n >= 10)
		return "";
	//init the permutation.
	string permu(n,'0');
	for(int i = 0; i < n; ++i)
		permu[i] = i + 1 + '0';

	if(k == 1) 
		return permu;
	while (k > 0)
	{
		int fac = checkFactorial(k);
		//adjust
		if(permu[n - 1] <= permu[n - fac])
		{
			nextPermutetion(permu);
		}

		reverse(permu.begin() + (n - fac), permu.end());
		k -= getFactorial(fac);
	}
	return permu;	
}

说明：实现有些复杂，http://blog.csdn.net/doc_sgl/article/details/12840715 这里有个简单的纯数学解法。


联系
我们