JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

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 for n = 3:

“123” “132” “213” “231” “312” “321” Given n and k, return the kth permutation sequence.

Note:

Given n will be between 1 and 9 inclusive. Given k will be between 1 and n! inclusive. Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Code

加入1,2,3,4四个数字
取第18个排列: 3412
那么先用17/6是看开头的数字是多少
因为每个数字开头都要有6种排列（因为3个数字有6种排列）
1-{2,3,4}-6种
2-{1,3,4}-6种
3-{1,2,4}-6种
4-{1,2,3}-6种
发现17/6 = 2 因此是以3开头的
然后把3从结果中去掉,开始看3个数字的情况,这时要把k = 17 % 6 = 5 得到在3个数的排列中是第几个

class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> nums = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            nums.add(i);
        }

        int[] fact = new int[n];
        fact[0] = 1;
        for(int i = 1; i < n; i++){
            fact[i] = fact[i - 1] * i;
        }

        k = k - 1;
        StringBuilder sb = new StringBuilder();
        for(int i = n - 1; i >= 0; i--){
            int num = nums.remove(k / fact[i]);
            sb.append(num);
            k %= fact[i];
        }

        return sb.toString();
    }
}