第k个排列

太过爱你忘了你带给我的痛 2022-01-20 03:49 279阅读 0赞

1、问题描述

给出集合 [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!]。

2、解法

2.1 找规律

  1. public String getPermutation(int n, int k) { 
  2.     StringBuilder sb = new StringBuilder();
  3.     int[] jc = new int[n+1];
  4.     jc[0] =1;
  5.     for(int i=1;i<n+1;i++) { 
  6.         jc[i] = i*jc[i-1];
  7.     }
  8.     List<Integer> list = new ArrayList<Integer>();
  9.     for(int i=1;i<=n;i++) { 
  10.         list.add(i);
  11.     }
  12.     //循环遍历，去计算每个位置上的数字
  13.     int curIndex=0;
  14.     while(n>0) { 
  15.         int t = jc[--n];
  16.         curIndex = (int)Math.ceil((double)k/(double)t) -1;
  17.         if(curIndex == -1) { 
  18.             curIndex = list.size()-1;
  19.         }
  20.         sb.append(list.get(curIndex));
  21.         k%=t;
  22.         list.remove(curIndex);
  23.     }
  25.     return sb.toString();
  26. }

发表评论

表情：
评论列表 （有 0 条评论，279人围观）

还没有评论，来说两句吧...

相关阅读