[C++] [0 ms] Illustrated O(n) solution


  • 1
    D

    This is mainly a mathematics problem. For a permutation set of digits, say 1,2,3,4:

    • 1 2 3 4
    • 1 2 4 3
    • 1 3 2 4
    • 1 3 4 2
    • 1 4 2 3
    • 1 4 3 2
    • 2 1 3 4
    • 2 1 4 3
      ....
    • 4 3 2 1

    As you can see, number of permutations start with "1" is 6 = (n-1)!. Similarly, number of permutations start with "2" is also (n-1)!. So, to determine the first number of the kth value, we only need to calculate (k-1)/(n-1)! . Once you get this number, remember to remove it from available digits list.

    Then, you move to the 2nd number. Everything stays the same, except your new k now becomes k%(n-1)!.

    And, Code (I don't know how to format, pasting code seems always get messed up...):

    
    /* Factorials, i.e. n! */
    int const factorials[] { /* 0! */ 1, /* 1! */ 1, /* 2! */ 2, /* 3! */ 6, /* 4! */ 24, /* 5! */ 120, /* 6! */ 720, /* 7! */ 5040, /* 8! */ 40320, /* 9! */ 362880 };
    
    class Solution {
    public:
        string getPermutation(int n, int k) {
            // Available charactors '1' ~ 'n'.
            vector<char> availableChars;
            for (int i = 0; i < n; i++)
            {
                availableChars.push_back('1' + i);
            }
    
            string result;
            k--;
    
            // Calculate the digit on each position.
            for (int i = 0; i < n; i++)
            {
                // Get the index of the digit in available digits set.
                int idx = k / factorials[n-i-1];
    
                // Add the digit to result string.
                result.push_back(availableChars[idx]);
    
                // Remove the digit from available digits set.
                availableChars.erase(availableChars.begin() + idx);
    
                // Adjust 'k'.
                k %= factorials[n - i - 1];
            }
    
            return result;
        }
    };
    
    

  • 0
    Y

    I think, that worst case complexity is O(n^2) for your code.
    In your for loop
    // Calculate the digit on each position. for (int i = 0; i < n; i++)
    you are erasing from vector. Worst case complexity for erasing from c++ vector is O(n). (if element which you want to erase is located in the beginning of the vector).


Log in to reply
 

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