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):

  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.

C++:
01 class Solution {
02 public:
03     string getPermutation(int n, int k) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         vector<char> A(n);
07         string result;
08         int cnt=1;
09         for(int i=0;i<n;i++)
10         {
11             A[i]=i+‘1’;
12         }
13         for(int i=1;i<n;i++)
14         {
15             cnt*=i;
16         }
17         for(int i=0;i<n;i++)
18         {
19             int t=(k1)/cnt;
20             k=kt*cnt;
21             if(i<n1)
22                 cnt=cnt/(ni1);
23             else
24                 cnt=1;
25             result+=A[i+t];
26             for(int j=i+t;j>i;j)
27                 A[j]=A[j1];
28         }
29         return result;
30     }
31 };
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s