第k个排列

题目描述

第k个排列 Permutation Sequence

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

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

说明： 给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。

示例 1:

输入: n = 3, k = 3 输出: “213”

示例 2:

输入: n = 4, k = 9 输出: “2314”

解决方案

1 . 结合上文的下一个排列，循环k-1次，nums即为所求序列。Java代码如下所示。

class Solution { public String getPermutation(int n, int k) { int nums[]=new int[n]; for (int i = 0; i < n; i++) { nums[i]=i+1; } for (int i = 0; i < k-1; i++) { nextPermutation(nums); } StringBuffer sb = new StringBuffer(); for (int i : nums) { sb.append(i); } return sb.toString(); } private void nextPermutation(int[] nums) { int j = 0, i = 0, temp = 0; labelb: for (i = nums.length - 2; i>= 0; i--) { for (j= nums.length - 1; j>i; j--) { if (nums[i] < nums[j]) { temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; break labelb; } } } Arrays.sort(nums, i+1, nums.length); } }

2 . 根据数字规律，也可以根据康托展开求解。