找到排列组合的第K个
一开始用backtrack,成功组合到第K个的时候返还。
果然TLE。。
然后看规律。
比如N = 4
1 - 2 3 4
2 - 1 3 4
3 - 1 2 4
4 - 1 2 3
就是4个 N=3的排列组合
同理 3 就是 3 个 N = 2的组合
public class Solution {
int[] dp;
public String getPermutation(int n, int k)
{
if(n == 1) return "1";
if(n == 2)
{
if(k == 1) return "12";
else return "21";
}
dp = new int[n];
Arrays.fill(dp,-1);
List<Integer> numList = new ArrayList<Integer>();
for(int m = 1; m <= n; m++)
{
numList.add(m);
}
String res = helper(n,k,numList);
return res;
}
public String helper(int n, int k, List<Integer> numList)
{
if(n == 1) return Integer.toString(numList.get(0));
if(n == 2)
{
if (k == 1) return Integer.toString(numList.get(0)) + Integer.toString(numList.get(1));
else return Integer.toString(numList.get(1)) + Integer.toString(numList.get(0));
}
int level = Combination(n-1);
int first;
first = k / level;
if(k % level == 0)
{
first = first;
}
else first = first + 1;
k = k % level;
if(first == 0) first = 1;
//System.out.println("level = " + level + " first = " + first + " k = " + k);
int removed = numList.remove(first-1);
if(k == 0)
{
k = level;
}
return Integer.toString(removed) + helper(n-1,k,numList);
}
public int Combination(int n )
{
if(dp[n-1] != -1) return dp[n-1];
if(n == 1 ) return 1;
int res = n * (Combination(n-1));
dp[n-1] = res;
return res;
}
}
二刷。
回头看自己一刷,觉得自己好牛逼。。以怎样的毅力做完的。。
二刷和一刷思路一样,简化了很多地方。Permutation从最大的开始往下除(n-1 to 1)
list.remove可以直接删除。
等等。。当时刚用Java可以理解吧。
public class Solution
{
public String getPermutation(int n, int k)
{
k--;
if(n == 1) return "1";
List<Integer> list = new ArrayList<>();
int left = 1;
for(int i = 1; i < n;i++)
{
list.add(i);
left*=i;
}
list.add(n);
int largest = n;
String res = new String();
while(largest >= 1)
{
res += Integer.toString(list.remove(k/left));
k%=left;
largest--;
if(largest == 0) break;
left/=largest;
}
return res;
}
}
二刷的问题是上来的K--没弄懂怎么个意思,但是比如2,2这种确实会抱错。
再比如3 4, P(2)= 2, 4/P(2)能整除,此时list里面是1 2 index = 4/P(2)=2 溢出了,所以此时应该index - 1,但是如果index = 0, -1又不对了。。
通过上来k--避免了这种情况,很巧妙。。