O(N) mathematical algorithm


  • -1
    Y
    int factorial(int n) {
        if(n==0 || n==1)
            return 1;
        int result = 1;
        for(int i=n; i>1; i--)
            result *= i;
        return result;
    }
    
    string getPermutation(int n, int k) {
        if(n==1)
            return "1";
        
        list<int> charList;
        for(int i=1; i<=n; i++)
            charList.push_back(i);
        
        string result = "";
        int idx = k-1;
        int divisor = factorial(n-1);
        int updateDivisor = n-1;
        
        while(charList.size()>1) {
            int quotient = idx/divisor;
            int residue = idx%divisor;
            list<int>::iterator itr = charList.begin();
            for(int i=0; i<quotient; i++)
                itr++;
            result += '0'+char(*itr);
            charList.erase(itr);
            idx = residue;
            divisor = divisor/updateDivisor;
            updateDivisor--;
        }
        result += '0'+char(*(charList.begin()));
        return result;
    }
    

    Given that n is fixed, the time complexity of this is O(N). It's not very concise, but it's another way to solve this problem !


Log in to reply
 

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