原题
给出集合 [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"
解法
思想
对于第一位，任一数字所占个数就是n-1的阶乘，那么可以通过先计算出1~n-1的阶乘，然后每一位按顺序递推。
代码
class Solution {
public String getPermutation(int n, int k) {
StringBuilder sb = new StringBuilder();
boolean[] used = new boolean[n];
int factorial[] = new int[n];
int count = 1;
factorial[0] = 1;
k -= 1;
for(int i = 1; i < n;i++){
factorial[i] = (count*=i);
}
for(int num = n-1;num >= 0 ; num--){
int pos = k / factorial[num];
k %= factorial[num];
for(int i = 0;i<n;i++){
if(!used[i]){
if(pos == 0) {
sb.append(i+1);
used[i] = true;
break;
}
pos -= 1;
}
}
}
return sb.toString();
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode60-%e7%ac%ack%e4%b8%aa%e6%8e%92%e5%88%97/
相关推荐
-
leetcode876-链表的中间结点
原题 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 示例 1: 输入： [1,2,3,4,5] 输出： 此列表中的结...
-
leetcode11-盛最多水的容器
原题 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i,...
-
leetcode75-颜色分类
原题 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 此题中，我们使用整数 0、 1 和 2 分...
-
leetcode154-寻找旋转排序数组中的最小值II
原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。...
-
leetcode1162-地图分析
原题 你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域...
-
leetcode1413-逐步求和得到正数的最小值
原题 给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。 你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums...
-
leetcode205-同构字符串
原题 给定两个字符串 s 和 t，判断它们是否是同构的。 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。 所有出现的字符都必须用另一个字符替换，同时保留字符的顺...
-
leetcode88-合并两个有序数组
原题 给定两个有序整数数组 nums1 和 nums2 ，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。 说明： 初始化 nums1 和 nums2 的...
-
leetcode217-存在重复元素
原题 给定一个整数数组，判断是否存在重复元素。 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。 示例1： 输入： [1,2,3...
-
leetcode189-旋转数组
原题 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。 示例1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4...
