首页 > 代码库 > [LeetCode] Permutation Sequence

[LeetCode] Permutation Sequence

2024-07-18 07:04:22   216人阅读

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 res;        func(res,n,k);        return res;    }private:    void func(string &res,int n,int k){ //n表示几位数        if(n==0)            return;        int weight = f(n-1);        char cur = ‘1‘;               int num = (k-1)/weight + 1;        while( find(res.begin(),res.end(),cur)==res.end() || num!=0){             if(find(res.begin(),res.end(),cur)==res.end())               num--;              if( num != 0)                 cur += 1;              else                  break;        }         k %= weight;        if(k==0)            k = weight;         res.push_back(cur);                    func(res,n-1,k);    }    int f(int n){              if(n == 1 || n==0)           return 1;       else          return n*f(n-1);        }};

 


联系
我们