C++ O(n) solution


  • 0
    H
    class Solution {
    public:
        string getPermutation(int n, int k) {
            vector<int> cnt(n+1, 1);
            for(int i = 1; i <= n; i ++) cnt[i] = i * cnt[i-1];
            vector<char> candidate;
            string ans = "";
            for(int i = 1; i <= n; i ++) candidate.push_back('0' + i);
            while(n > 0) {
                int idx = (k - 1) / cnt[n-1];
                ans += candidate[idx];
                candidate.erase(candidate.begin() + idx);
                k -= idx * cnt[n-1];
                n --;
            }
            return ans;
        }
    };
    

  • 0
    L

    not o(n), I guess vector.erase() needs o(n) time.


  • 0

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.