获取1~n全排列从小到大排列的第k个值

青旅半醒 2021-09-26 14:54 239阅读 0赞

问题描述：

> 给出集合 \[1,2,3,…,n\]，其所有元素共有 n! 种排列。
> 
> 按大小顺序列出所有排列情况，并一一标记，  
> 可得到如下序列 (例如, n = 3)：
> 
> “123”  
> “132”  
> “213”  
> “231”  
> “312”  
> “321”  
> 给定 n 和 k，返回第 k 个排列序列。
> 
> 注意：n 介于1到9之间（包括9）。  
> 思路：  
> 我的思路是每次求出k /(n-1)!,通过这样来判断本次的第一个数字是什么。  
> 比如说 n = 3,k = 4，那么1位数字开头的可能有2！种，而4/2 =2,证明我需要的数字是以2开头。然后在2开头的排列组合中找到第2个数字，这个寻找过程与上一步类似，每次查找时序注意已经经使用过的数字不能再使用。（本人语言表达能力不好，可能代码更好看懂些）

Java实现如下：

class Solution { 
        public String getPermutation(int n, int k) {
            int[] arr = new int[]{
       1,1,2,6,24,120,720,5040,40320,363880};//记录0-9的阶乘
            boolean[] isUsed = new boolean[10];//标记已经使用过的数字
            StringBuilder sBuilder = new StringBuilder();//答案字符串
            int index = n;//待确定的数据位置，可根据这个计算(index-1)!
            int temp1 = 0;//临时变量 记录 k/arr[index-1]
            int temp2 = 0;//临时变量 记录 k%arr[index-1]
            while(k>0&&index>0){
                //System.out.println(k+" "+index);
                temp1 = k/arr[index-1];
                temp2 = k%arr[index-1];
                //根据temp1和temp2更新k值，然后计算出当前是第temp1个未被使用的数字
                if(temp2!=0){
                    temp1=temp1+1;
                    k = temp2;
                }else{
                    k = arr[index-1];
                }
                //找到第temp1个未使用的数字
                int count = 0;
                for(int i = 1;i<= n;i++){
                    if(isUsed[i]==false){
                        count++;
                        if(count == temp1){
                            sBuilder.append(i);
                            isUsed[i] = true;
                            break;
                        }
                    }               
                }   
                index--;            
            }
            return sBuilder.toString();    
        }
    }