返回第k个排列

package go.jacob.day801;

import java.util.ArrayList;
import java.util.List;

/**
 * 60. Permutation Sequence
 * @author Jacob
 *
 */
public class Demo1 {
	/*
	 * 在n!个排列中，第一位的元素总是(n-1)!一组出现的，也就说如果p = k / (n-1)!，
	 * 那么排列的最开始一个元素一定是nums[p]。
	 * 
	 * 假设有n个元素，第K个permutation是 a1, a2, a3, ..... ..., an 那么a1是哪一个数字呢？
	 * 那么这里，我们把a1去掉，那么剩下的permutation为 a2, a3, .... .... an, 共计n-1个元素。
	 * n-1个元素共有(n-1)!组排列，那么这里就可以知道 设变量K1 = K a1 = K1 / (n-1)! 
	 * 同理，a2的值可以推导为 a2 =K2 / (n-2)! K2 = K1 % (n-1)! ....... a(n-1) = K(n-1) / 1! 
	 * K(n-1) = K(n-2)/2! 
	 * an = K(n-1)
	 */
	public String getPermutation(int n, int k) {
		// 存储阶乘
		int[] factorial = new int[n + 1];
		factorial[0] = 1;
		int sum = 1;
		for (int i = 1; i <= n; i++) {
			sum *= i;
			factorial[i] = sum;
		}
		// 如果k越界，返回null
		if (k > factorial[n])
			return null;
		System.out.println("lalal");
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < n; i++)
			list.add(i + 1);
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= n; i++) {
			int index = (k - 1) / factorial[n - i];
			sb.append(list.get(index));
			list.remove(index);
			k = k - index * factorial[n - i];
		}

		return sb.toString();
	}
}

最开始用暴力全排序的方法，直接超时，但是感觉在本地测试，速度没那么慢，毕竟1<n<=9;
暴力不行只能另想办法。
第一个数一定是123...n，所以第一位以1开头的数有（n-1）！种可能，
所以第二位以某个数开头有（n-2）!中可能
同理...
所以我们求每一位上的值是多少？
第一位是多少呢？
k/(n-1)!
第二位是多少呢？
k=k%(n-1)!
k/(n-2)!
同理一直算到最后一位数。
下面给出代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Solution {
    public  String getPermutation(int n, int k) {
        k--;//我们算法中是k从0开始，题意从1开始，所以我们要k--;
        int num[]=new int[n];
        int cnt=1;
        for(int i=0;i<n;i++)
        {
            num[i]=i+1;//初始化{1,2,3,...,n}
            cnt*=(i+1);//求n!
        }
        char[] cs=new char[n];//保存每一位结果
        for(int i=0;i<n;i++)
        {
            cnt/=(n-i);
            int selected=k/cnt;
            cs[i]=(char) ('0'+num[selected]);
            for(int j=selected;j<n-1-i;j++)
            {
                num[j]=num[j+1];
            }
            k%=cnt;
        }
        return new String(cs);
    }



}

全排列暴力递归法也是可以的啊！

public class PermutationSequence {

  int count;
  String result;

  public String getPermutation(int n, int k) {
    char[] arr = new char[n];
    for (int i = 0; i < n; i++)
      arr[i] = (char) ('1' + i);
    permutation(arr, 0, k);
    return result;
  }

  private void permutation(char[] arr, int index, int cc) {
    //至于什么时候输出，要考虑清楚
    //考虑：只有所有位置上的字符都确认即index到达末尾，才算是排好一种情况
    if (index == arr.length) {
      count++;
      // System.out.println(String.valueOf(arr));
      if (count == cc)
        result = String.valueOf(arr);
    }
    //现在index之前的字符都已就位，把之后的每个字符都交换到index这个位置
    for (int k = index; k < arr.length; k++) {
      //尝试交换
      swap1(arr, index, k);
      //交换之后index这个位置就定好了，接下来的事就是递归去解决index+1位置开始的全排列就好了
      permutation(arr, index + 1, cc);
      // 前面我们尝试交换，把全排列求出来了，交换时只尝试了一个字符，因此for循环继续之前要换回来，继续尝试交换下一个字符
      swap2(arr, index, k);
    }
  }

  private void swap1(char[] arr, int index, int k) {
    char tmp = arr[k];
    //用插入法不改变后续元素的大小顺序
    for (int i = k; i > index; i--) {
      arr[i] = arr[i - 1];
    }
    // arr[k] = arr[index];
    arr[index] = tmp;
  }

  private void swap2(char[] arr, int index, int k) {
    char tmp = arr[index];
    //用插入法不改变后续元素的大小顺序
    for (int i = index; i < k; i++) {
      arr[i] = arr[i + 1];
    }
    arr[k] = tmp;
  }

  public static void main(String[] args) {
    Instant now = Instant.now();
    System.out.println(new PermutationSequence().getPermutation(9,362880));
    System.out.println(Instant.now().toEpochMilli()-now.toEpochMilli());
  }
}

string getPermutation(int n, int k) {
        // 计算n-1位数字共有多少种组合，便可以求出来第k个组合是以哪个数字开头
        // 之后将第一位数字去除，再计算n-2位数字共有多少种组合，...

        // 预先将n!(n = 1 ~ n - 1)存起来
        vector<int> rec(n, 1);
        for (int i = 2; i < n; i ++) rec[i] = i * rec[i - 1];
        vector<int> data(n, 0);
        for (int i = 0; i < n; i ++) data[i] = i + 1;

        string res = "";
        for (int i = 1; i < n && k >= 1; i ++ ) {
            // 若当前k可以整除n-i位数字的全排列个数时，digit就是商；
            // 当无法整除时，需要再额外+1，才是最终的digit
            int tmp = k / rec[n - i];
            int digit = k % rec[n - i] == 0 ? tmp : tmp + 1;
            int num = data[digit - 1];
            data.erase(remove(data.begin(), data.end(), num), data.end());
            // 前面已经有了t = (digit - 1) * rec[n - i]个数字，需要再去计算余下的第(k - t)个数字
            k = k - (digit - 1) * rec[n - i];
            res += to_string(num);
        }
        
        // k=1时，表明后面的几位按照顺序来就可以了，所以将data中剩余的都加进去
        for (auto d: data) {
            res += to_string(d);
        }

        return res;
    }

public class Solution {
    String res = "";
    int count = 0;
    public String getPermutation(int n, int k) {
        int[] num = new int[n];
        for(int i=1; i<=n; i++){
            num[i-1] = i;
        }
        backTrack(num, k, n, "");
        return res;
    }
    void backTrack(int[] n, int k, int t, String str) {
        if(t == 0) {count ++; res = ""+str; return;} //t==0时，一个组合完成
        for(int i=0; i<n.length; i++){
            if(n[i] == 0) continue;
            str += n[i];
            n[i] = 0;
            backTrack(n, k, t-1, str);
            if(count == k) break;
            n[i] = i+1;
            str = str.substring(0, str.length()-1);
        }
        
    }
    
}

public class Solution {
    public String getPermutation(int n, int k) {
        boolean num[] = new boolean[n+1];
        int total = 1;
        for(int i=1; i<=n; i++) total *= i;
        return getResult(num,total,  n, k );
    }
    public String getResult(boolean num[],  int total, int n, int k){
        if(n == 0) return "";
        total = total / n;                 //相同开头数字有多少种变化 比如123 132两种 ，总共6种  6 / 3 = 2
        int count  = (k - 1) / total + 1;  //开头是余下n个数字的第几个数字（相当于第几行）  
        int next_k = (k - 1) % total + 1;  //相当于第几列                                                                                 
        int i = 1;                                                                    
        while(count > 0){  //找第count个没用过的数字
            if(!num[i]) count--;                         i++;
        }
        i--;
        num[i] = true; // 数字i用完，设为true
        return String.valueOf(i)+getResult(num, total, n-1, next_k);         }
}

class Solution {
public:
    int numb;
    vector<int> num;
    void gethelp(int n)
    {       
        num.clear();
        numb=1;
        for(int i=1;i<=n;i++)
        {
            numb*=i;
            num.push_back(i);            
        }       
    }
    string getPermutation(int n, int k) 
    {
        gethelp(n);
        string out="";
        k--;
        for(int i=0;i<n;i++)
        {
            numb/=(n-i);
            int tp=k/numb;
            out+=char('0'+num[tp]);
            for(int j=tp;j<n;j++)
               num[j]=num[j+1];
            k%=numb;
        }

        return out;
    }
};

import java.util.ArrayList;

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

        return find(dict, k - 1, n);
    }

    public String find(ArrayList<String> dict, int k, int n) {
        if (n == 1) return dict.get(0);

        int num = count(n - 1);
        int index = k / num;
        int offset = k % num;

        String s = dict.get(index);
        dict.remove(index);
        k = offset;

        return s + find(dict, k, n - 1);
    }


    public int count(int x) {
        if (x == 1) return 1;
        return x * count(x - 1);
    }
}

暴力我交了一次  超时了  
然后在网上发现这个办法   第一位有n种情况  每一种情况后面对应（n-1）！种可能 
那么第一位选择整个数组中的哪一位  就为k/（n-1）！ 
至于为什么k--  是因为当k==1  但是此时又两个数的时候1/（2-1）！==1  但是其实应该要的是0  所以k-1解决了这个边界问题
public class Solution {
    public String getPermutation(int n, int k) {
        if(k<=0 || n<0){
			 return "";
		 }
		 //求n的阶乘
		 int factorial  =1;
		 StringBuffer buffer = new StringBuffer();//用来存储1--n
		 StringBuffer result = new StringBuffer();
		 for(int i=1;i<=n;i++){
			 factorial *=i;
			 buffer.append(i+"");
		 }
		 k--;
		 for(int i=0;i<n;i++){//对于每一位
			 factorial = factorial/(n-i);
			 int index = k/factorial;
			 result.append(buffer.charAt(index));
			 //移除这个index
			 buffer.deleteCharAt(index);
			 k = k%factorial;
		 }
		return result.toString();    
    }
}

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> num(n,0);
        string str = "";
        for(int i = 0; i < n; ++ i) num[i] = i+1;
        for(int i = 0; i < k-1; ++ i)
            next_permutation(num.begin(),num.end());
        for(int i = 0; i < n; ++ i) str += num[i]+'0';
        return str;
    }
};

class Solution {
public:     int N = 0;     vector<int> d;     string result = "";     int book[15] = {0};
    string getPermutation(int n, int k) {
        DFS(0, n, k);
        return result;
    }
    void DFS(int step, int n, int k)
    {
        int i;
        if(step == n)
        {
            N++;
            if(N == k)
                for(int i=0;i<d.size();i++)
                    result += d[i] + '0';         }else{             for(int i=1;i<=n;i++)             {                 if(book[i] == 0)                 {                     d.push_back(i);                     book[i] = 1;                     DFS(step+1, n, k);                     book[i] = 0;                     d.pop_back();                 }             }         }     }
};

public String getPermutation(int n, int k) {
        String res="";
        ArrayList<Integer> list =new ArrayList<>();
        for(int i=0;i<n;i++)
            list.add(i+1);
        int[] f = new int[n];
        f[0]=1;
        k--;
        for(int i=1;i<n;i++) f[i]=f[i-1]*i;
        for(int i=n;i>=1;i--){
            int j=k/f[i-1];
            k%=f[i-1];
            res+=list.get(j);
            list.remove(j);
        }
        System.out.println(res);
        return res;
    }

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int count = 0;
    static String res = "";

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

    public static String getPermutation(int n, int k) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        backTrack(list, k, n, "");
        return res;
    }

    static void backTrack(List<Integer> list, int k, int num, String str) {
        if (num == 0) {
            count++;
            res = "" + str;
            return;
        }
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).equals(0)) {
                continue;
            }
            str += list.get(i);
            list.set(i, 0);
            backTrack(list, k, num - 1, str);
            if (count == k) {
                break;
            }
            list.set(i, i+1);
            str = str.substring(0, str.length() - 1);
        }

    }
}

C++求排列有三种方法：

1. 利用库函数next_permutation
2. 基于交换
3. 基于回溯

下面用库函数next_permutation求：

//
// Created by jt on 2020/9/26.
//
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    /**
     *
     * @param n int整型
     * @param k int整型
     * @return string字符串
     */
    string getPermutation(int n, int k) {
        // write code here
        vector<char> vec;
        for (int i = 1; i <= n; ++i) vec.push_back(i+'0');
        while (--k > 0 && next_permutation(vec.begin(), vec.end())) {}
        return string(vec.begin(), vec.end());
    }
};

import java.util.*;


public class Solution {
    /**
     * 回溯法
     * @param n int整型 
     * @param k int整型 
     * @return string字符串
     */
    private  String str = "";
    private  int pos;
    public String getPermutation (int n, int k) {
        if (n <=0 || k <= 0){
            return null;
        }
        pos = k;
        backTrack(n,new ArrayList<>());
        return str;
    }
    
    public  void backTrack(int n, ArrayList<Integer> list){
        if (list.size() == n ){
            pos--;
            if (pos == 0){
                for (Integer integer : list) {
                    str += integer;
                }
            }
        }else if (pos > 0){
            for (int i = 1; i <= n ; i++) {
                if (!list.contains(i)){
                    list.add(i);
                    backTrack(n,list);
                    list.remove(list.size() - 1);
                }
            }
        }
    }
}

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> factorial(n+1,0);//记录1~n的阶乘
        factorial[0]=1; //特别注意的是0的阶乘是1，也就是说当到了最后一层时，可供选择的方案是1而不是0，这点一定要注意
        for(int i=1;i<n+1;i++) {
            factorial[i]=factorial[i-1]*i;
        }
        set<int> ST;//记录哪些数以及在递归路径上了
        string s="";//
        int deep=1;//记录处在递归树的第几层
        Recursive(deep,k,n,s,factorial,ST);
        return s;
    }
    void Recursive(int deep,int k,int n,string &s,vector<int> &factorial,set<int> &ST) {
        if(s.length()==n) {
            return ;
        }
        for(int i=1;i<n+1;i++) {
            if(ST.find(i)!=ST.end()) continue;
            ST.insert(i);
            if(factorial[n-deep]>=k) s=s+to_string(i);//当某层的单个分支大于等于剩余的k，就将这一层存入
            if(factorial[n-deep]<k) {//当某层的单个分支小于剩余的k，就切换到下一个分支，注意切换到同一层其他分支时要，注意将当前分支的根节点从ST中移除ST
                k-=factorial[n-deep];
                ST.erase(ST.find(i));
                continue; 
            }
            Recursive(deep+1,k,n,s,factorial,ST); //当某层的单个分支大于等于剩余的k，进入下一层
        }
    }
};