4.30 leetcode -30 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): "123" "132" "213" "231" "312" "321" Given n and k, return the k th permutation sequence.

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

这个题目吧，全排列，然后还是从小到大排序，那么就可以直接算得第n个数是啥。算法为：

class Solution { public: string getPermutation(int n, int k) { bool * bnumber = (bool *)malloc(n*sizeof(bool)); int num = 1; string pstring(n,'0'); for(int i = 0;i < n; i++) { bnumber[i] =true; if(i != 0) num*=i; } k = k - 1; for(int i = 0; i < n; i++) { int tmp = k/num; for(int j = 0 ;j < n;j++) { if(bnumber[j] == true) tmp --; if(tmp == -1) { pstring[i] = (j + 1 + '0'); bnumber[j] = false; break; } } k = k%num; if( i != (n - 1)) num = num/(n - 1- i); } return pstring; } };