60. 第k个排列

题意：

解题思路：

思路：
首先我们将所有排列按首位分组：
1 + (2, 3, 4的全排列)
2 + (1, 3, 4的全排列)
3 + (1, 2, 4的全排列)
4 + (2, 3, 4的全排列)
接下来我们确定第 k=14个排列在哪一组中。
每组的排列个数是 3! = 6个，所以第14个排列在第3组中，所以首位已经可以确定，是3。
然后我们再将第3组的排列继续分组：
31 + (2, 4的全排列)
32 + (1, 4的全排列)
34 + (1, 2的全排列)
接下来我们判断第 k=14个排列在哪个小组中。
我们先求第14个排列在第三组中排第几，由于前两组每组有6个排列，所以第14个排列在第3组排第 14−6∗2=2。
在第三组中每个小组的排列个数是 2! = 2个，所以第 k 个排列在第1个小组，所以可以确定它的第二位数字是1。
31 + (2, 4的全排列) => 3124 3142
由于2，4的最大排列为2，所以12 + 2 = 14，所以答案是3142

PHP代码实现：

class Solution {
    /**
     * @param Integer $n
     * @param Integer $k
     * @return String
     */
    function getPermutation($n, $k) {
        $fact = 1;
        $nums = [];
        for ($i = 0; $i < $n; $i++) {
            $nums[$i] = $i + 1;
            $fact *= $i + 1;
        }
        $k -= 1;
        $res = "";
        for ($i = 0; $i < $n; $i++) {
            $fact = floor($fact / ($n - $i));
            $index = floor($k / $fact);
            $res .= (string) $nums[$index];
            $k %= $fact;
            unset($nums[$index]);
            $nums = array_values($nums);
        }
        return $res;
    }
}

GO代码实现：

func getPermutation(n int, k int) string {
    // offset k
    k = k - 1
    // build stack of permutations and an array from 1 to n
    permStack := []int{}
    nums := []int{1}
    currentP := 1
    for i := 2; i <= n; i++ {
        nums = append(nums, i)
        permStack = append(permStack, currentP)
        currentP = currentP*i
    }
    // build result
    result := ""
    for len(nums) > 1 {
        // pop from stack
        perm := permStack[len(permStack)-1]
        permStack = permStack[:len(permStack)-1]
        // find index
        idx := k/perm
        // find next k
        k = k%perm
        // add num at index to result
        result = result + strconv.Itoa(nums[idx])
        // delete num at index
        copy(nums[idx:], nums[idx+1:])
        nums = nums[:len(nums)-1]
    }
    return result + strconv.Itoa(nums[0])
}