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.

 class Solution {
public:
string getPermutation(int n, int k) {
string result;
bool used[];
memset(used, false, );
int base[];
base[] = ;
for (int i = ; i <= n; ++i) {
base[i] = base[i - ] * i;
}
--k;
for (int i = ; i < n; ++i) {
int p = k / base[n - - i];
for (int j = ; j <= n; ++j) {
if (!used[j] && p-- == ) {
result.push_back('' + j);
used[j] = true;
break;
}
}
k %= base[n - - i];
}
return result;
}
};

n个数组的全排列中,以1开头的个数(n-1)!个,同样以2..n开头的个数有(n-1)!个,这样根据(k-1)/[(n-1)!]可知第一个数是多少,依次类推...

05-11 17:48
查看更多