每天一道算法题之第K个排列

第K个排列

题目描述: 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

“123” “132” “213” “231” “312” “321” 给定 n 和 k，返回第 k 个排列。

解析:

从数学的排列组合可知以i(1<=i<=n)起始数字的排列共有(n-1)!种.如果第二个位置上的数字是j(j != i),那么此时共有 (n-2)! 种排列.

如果$m_1$(n-1)! <k<($m_1$+1)(n-1)!, 那么第一个位置应该取 $m_1$.此时可选元素变为n-1个. $m_1=k/(n-1)!$, 更新k, k $\%=(n-1)!$

如果$m_2$(n-2)! <k<($m_2$+1)(n-2)!, 那么第一个位置应该取$m_2$.此时可选元素变为n-2个. $m_2=k/(n-2)!$, 更新k, k $\%=(n-2)!$ …

注: $m_1$,k表示第几个元素并非索引,写代码时要注意

代码部分:

public static String getPermutation(int n, int k) { int[] f = new int[n]; f[0] = 1; for(int i = 1;i<n;i++){ f[i] = i*f[i-1]; } List<Integer> nums = new ArrayList<>(); for(int i = 1;i<=n;i++){ nums.add(i); } k--;//错位,索引从0开始 StringBuilder sb = new StringBuilder(); for(int i = n-1;i>=0;i--){//总共是n个数 int idx = k/f[i]; sb.append(nums.get(idx)); nums.remove(nums.get(idx));//将使用后的数字删除 k %= f[i]; } return sb.toString(); }