leetcode60-第k个排列

原题

给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

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

给定 n 和 k,返回第 k 个排列。

说明:

  • 给定 n 的范围是 [1, 9]。
  • 给定 k 的范围是[1,  n!]。

示例 1:

输入: n = 3, k = 3
输出: "213"

示例 2:

输入: n = 4, k = 9
输出: "2314"

解法

思想

对于第一位,任一数字所占个数就是n-1的阶乘,那么可以通过先计算出1~n-1的阶乘,然后每一位按顺序递推。

代码

class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder sb = new StringBuilder();
        boolean[] used = new boolean[n];
        int factorial[] = new int[n];
        int count = 1;
        factorial[0] = 1;
        k -= 1;
        for(int i = 1; i < n;i++){
            factorial[i] = (count*=i);
        }
        for(int num = n-1;num >= 0 ; num--){
            int pos = k / factorial[num];
            k %= factorial[num];
            for(int i = 0;i<n;i++){
                if(!used[i]){
                    if(pos == 0)  {
                        sb.append(i+1);
                        used[i] = true;
                        break;
                    }
                    pos -= 1;
                }
            }
        }
        return sb.toString();
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode60-%e7%ac%ack%e4%b8%aa%e6%8e%92%e5%88%97/

发表回复

登录后才能评论