Day 80, #60, Permutation Sequence

Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
-----------------------------------------------------------------------------
Factorial. Lay out permutations, you will see the pattern
将k设为0-base

class Solution {
public:
    int getFactorial(int n) {
        int rt = 1;
        for (int i = 1; i <= n; i++) {
            rt *= i;
        }
        
        return rt;
    }

    int getNextNumber(vector<bool> &nums, int section) {
        for (int i = 0; i < nums.size(); i++) {
            if (section == 0 && nums[i] == false) {
                nums[i] = true;
                return i;
            }
            if (nums[i] == false) {
                section--;
            }
        }
    }

    string getPermutation(int n, int k) {
        int factorial = getFactorial(n);
        string rt = "";
        vector<bool> nums(n,false);
        k--;
        for (int i = n; i > 0; i--) {
            factorial /= i;
            int section = k / factorial;
            k = k % factorial;
            char c = getNextNumber(nums,section) + '1';
            rt += c;
        }
        
        return rt;
    }
};