题目

60. 第k个排列

题解

直接用回溯法做的话需要在回溯到第k个排列时终止，这样就不会超时了, 但是效率很低，所以排除回溯法。

此题应该用“康托展开”的思路进行求解。




代码

1. 超时代码：

import java.util.*;

public class code60 {

    public static String getPermutation(int n, int k) {
        int nums[] = new int[n + 1];
        for (int i = 1; i < nums.length; i++) {
            nums[i] = i;
        }
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        int visit[] = new int[nums.length];
        dfs(res, list, nums, visit);
        int count = 0;
        String str = "";
        for (List<Integer> x : res) {
            count++;
            if (count == k) {
                str = x.toString();
            }
        }
        char c[] = new char[15];
        int sum = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) > '0' && str.charAt(i) <= '9') {
                c[sum++] = str.charAt(i);
            }
        }
        char temp[] = new char[sum];
        for (int i = 0; i < sum; i++) {
            temp[i] = c[i];
        }
        String ans = String.valueOf(temp);
        return ans;
    }

    public static void dfs(List<List<Integer>> res, List<Integer> list, int nums[], int visit[]) {
        if (list.size() == nums.length - 1) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 1; i <= nums.length - 1; i++) {
            if (visit[i] == 0) {
                visit[i] = 1;
                list.add(nums[i]);
                dfs(res, list, nums, visit);
                visit[i] = 0;
                list.remove(list.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            String res = getPermutation(n, k);
            System.out.println(res);
        }
    }
}

2. 执行用时约1秒钟的代码：

import java.util.*;

public class code60 {

    public static int count;
    public static List<Integer> finalRes;

    public static String getPermutation(int n, int k) {
        count = 0;
        finalRes = new ArrayList<>();

        int nums[] = new int[n + 1];
        for (int i = 1; i < nums.length; i++) {
            nums[i] = i;
        }
        // 第几个解
        List<Integer> tempRes = new ArrayList<>();
        int visit[] = new int[nums.length];
        dfs(nums, k, tempRes, visit);
        StringBuilder res = new StringBuilder();
        for (Integer i : finalRes) {
            res.append(i);
        }
        return res.toString();
    }

    public static void dfs(int nums[], int k, List<Integer> tempRes, int visit[]) {
        if (tempRes.size() == nums.length - 1) {
            count++;
            if (count == k) {
                finalRes = new ArrayList<>(tempRes);
                return;
            }
        }
        for (int i = 1; i <= nums.length - 1; i++) {
            if (visit[i] == 0) {
                visit[i] = 1;
                tempRes.add(nums[i]);
                dfs(nums, k, tempRes, visit);
                visit[i] = 0;
                tempRes.remove(tempRes.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            String res = getPermutation(n, k);
            System.out.println(res);
        }
    }
}

3. 康托展开代码：

import java.util.*;

public class code60 {

    // public static int count;
    // public static List<Integer> finalRes;

    // public static String getPermutation(int n, int k) {
    // count = 0;
    // finalRes = new ArrayList<>();

    // int nums[] = new int[n + 1];
    // for (int i = 1; i < nums.length; i++) {
    // nums[i] = i;
    // }
    // // 第几个解
    // List<Integer> tempRes = new ArrayList<>();
    // int visit[] = new int[nums.length];
    // dfs(nums, k, tempRes, visit);
    // StringBuilder res = new StringBuilder();
    // for (Integer i : finalRes) {
    // res.append(i);
    // }
    // return res.toString();
    // }

    // public static void dfs(int nums[], int k, List<Integer> tempRes, int visit[])
    // {
    // if (tempRes.size() == nums.length - 1) {
    // count++;
    // if (count == k) {
    // finalRes = new ArrayList<>(tempRes);
    // return;
    // }
    // }
    // for (int i = 1; i <= nums.length - 1; i++) {
    // if (visit[i] == 0) {
    // visit[i] = 1;
    // tempRes.add(nums[i]);
    // dfs(nums, k, tempRes, visit);
    // visit[i] = 0;
    // tempRes.remove(tempRes.size() - 1);
    // }
    // }
    // }

    // X = a[n]*(n-1)! + a[n-1]*(n-2)! + ... + a[i]*(i-1)! + ... + a[1]*0!
    public static String getPermutation(int n, int k) {
        int fac[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320 };
        StringBuilder sb = new StringBuilder();
        int visit[] = new int[10];
        k--;
        for (int i = n - 1; i >= 0; i--) {
            int t = k / fac[i];
            for (int j = 1; j <= n; j++) {
                if (visit[j] == 0) {
                    if (t == 0) {
                        sb.append(j);
                        visit[j] = 1;
                        break;
                    }
                    t--;
                }
            }
            k = k % fac[i];
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            String res = getPermutation(n, k);
            System.out.println(res);
        }
    }
}

参考：

  1. 【Leetcode】60. 第k个排列
  2. 浅谈生成全排列的4种方法
  3. 字符串、字符数组、list之间相互转化
  4. java 数组转换成String方法
  5. java将字符串和字符串数组互相转换方法
  6. 回溯 + 剪枝（Python 代码、Java 代码）——题解一
  7. C++ 非递归 康托展开思路实现——题解二
  8. 回溯法或者公式法——题解三
  9. 康托展开——百度词条
  10. 康托展开——维基百科
  11. 康托展开和逆康托展开
  12. 康托展开及其逆运算 详解

附：

一、康托展开及其逆运算的代码模板（C语言版）：

1. 康托展开：

int  fac[] = {1,1,2,6,24,120,720,5040,40320}; //i的阶乘为fac[i]
// 康托展开 -> 表示数字a是 a的全排列中从小到大排，排第几
// n表示1~n个数 a数组表示数字。
int kangtuo(int n,char a[])
{
    int i,j,t,sum;
    sum=0;
    for( i=0; i<n ;++i)
    {
        t=0;
        for(j=i+1;j<n;++j)
            if( a[i]>a[j] )
                ++t;
        sum+=t*fac[n-i-1];
    }
    return sum+1;
}

2. 康托展开的逆：

int  fac[] = {1,1,2,6,24,120,720,5040,40320};
//康托展开的逆运算,{1...n}的全排列，中的第k个数为s[]
void reverse_kangtuo(int n,int k,char s[])
{
    int i, j, t, vst[8]={0};
    --k;
    for (i=0; i<n; i++)
    {
        t = k/fac[n-i-1];
        for (j=1; j<=n; j++)
            if (!vst[j])
            {
                if (t == 0) break;
                --t;
            }
        s[i] = '0'+j;
        vst[j] = 1;
        k %= fac[n-i-1];
    }
}

二、提交时间依次减少：