Share my c++ solution of O(N^2) in 4ms


  • 0
    L
        int Factorial(int n) {
        static vector<int> flag = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
        return flag[n];
    }
    
    // rank is between 1 to n.
    int currentNum(vector<int> &isUsed, int n, int rank) {
        int count = 0;
        for (int i = 0; i < n; ++i) {
            if (isUsed[i] == false) {
                count++;
                if (count == rank) {
                    isUsed[i] = true;
                    return i + 1;
                }
            }
        }
        cerr << "fatal error" << endl;
        exit(-1);
    }
    
    string getPermutation(int n, int k) {
    	vector<int> isUsed(n, false);
        string result("");
        for (int i = 0; i < n; ++i) {
            int rank = (k - 1) / Factorial(n - i - 1) + 1;
            result.push_back(currentNum(isUsed, n, rank) + '1' - 1);
            k = k % Factorial(n - i - 1);
            if (k == 0) {
                k = Factorial(n - i - 1);
            }
        }
        return result;
    }

Log in to reply
 

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