排列序列
问题链接:https://leetcode-cn.com/problems/permutation-sequence
一、问题描述
给出集合 [1,2,3,...,n],其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k,返回第 k 个排列。
示例 1:
输入:n = 3, k = 3
输出:"213"
示例 2:
输入:n = 4, k = 9
输出:"2314"
示例 3:
输入:n = 3, k = 1
输出:"123"
提示:
1 <= n <= 9
1 <= k <= n!
二、问题分析
因为存在n!种排列,所以暴力求解不可能实现,那么就考虑回溯法,首先需要一个长度为n的数组,用来记录集合种元素的使用情况,当数组中元素全部被使用,就到达递归边界。每到达一个递归边界k的值就--,当k的值为0时,就返回该递归边界的排列。为了保证本次递归到了边界,所以还需要一个size变量,当size变量变成0,说明已经排列完成了,那么此时就产生了一个序列,再根据k的值判断该序列是否为要找的序列。
三、代码
1 class Solution { 2 public String getPermutation(int n, int k) { 3 int[] flag = new int[n]; 4 int[] ka = {k}; 5 StringBuffer str = new StringBuffer(); 6 rollback(str,ka,n,flag,n); 7 return str.toString(); 8 } 9 public void rollback(StringBuffer str,int[] ka,int n,int[] flag,int size){ 10 if(size==0&&ka[0]==0){ 11 return; 12 }else if(size==0&&ka[0]!=0){ 13 ka[0]--; 14 return; 15 }else if(ka[0]!=0){ 16 for(Integer i=1;i<=n;i++){ 17 if(flag[i-1]==0){//标记为0,说明没有被使用 18 str.append(i); 19 flag[i-1]=1; 20 rollback(str,ka,n,flag,size-1); 21 if(ka[0]!=0){ 22 flag[i-1]=0; 23 str.deleteCharAt(str.length()-1); 24 } 25 } 26 } 27 } 28 } 29 }
代码可以执行,不过很费时间