C++ 0ms Iterative Solution


  • 0
    A
    class Solution {
    public:
        string getPermutation(int n, int k) {
            string ans = "";
            int fact[9] = {1};
            for (int i = 1; i <= n; ++i) {
                if (i != n) fact[i] = fact[i-1] * (i+1);
                ans += (i + '0');
            }
            --k; 
            int curr = 0;
            while (k){
                int steps = k / fact[n-2];
                int next = curr + steps;
                k %= fact[n-2]; 
                if (steps != 0) ans[curr] ^= ans[next] ^= ans[curr] ^= ans[next];
                ++curr;
                if (steps > 1){
                    char tmp = ans[next];
                    while (next > curr){
                        ans[next] = ans[next-1];
                        --next;
                    }
                    ans[next] = tmp;
                }
                --n;
            }
            return ans;
        }
        
    };

Log in to reply
 

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