[leetcode] Permutation Sequence


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.

tag里说可以用回溯。我直接用了递归。o(n)的复杂度。

每次层递归时通过一个除法确定第一个字符,通过一个取余确定接下来字符串确定的index。

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<char> elements;
        for(int i = 1; i <= n; i++){
            elements.push_back(i + '0');
        }
        return _getPermutations(elements, k - 1);
    }
    string _getPermutations(vector<char> elements, int k){
        
        int size = elements.size();
        if(size == 1){//base condition
            return string(1, elements[0]);
        }
        int factorial = 1;
        for(int i = 1; i < size; i++){
            factorial *= i;
        }
        int reminder = k % factorial;
        int q = k / factorial;
        char c = elements[q];
        elements.erase(elements.begin() + q);
        string re = _getPermutations(elements, reminder);
        re.insert(re.begin(), c);
        return re;
    }
};

Selection_032

 

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.