前言
猛起更新。
正文
问题来源
本问题来自leetcode上的60题。
问题描述
给出集合 [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"
分析：
func reverse(nums []byte, start, end int) {
for start < end {
nums[start], nums[end] = nums[end], nums[start]
start++
end--
}
}
func nextPermutation(nums []byte) {
var i int
num_l := len(nums)
if num_l <= 1 {
return
}
for i = num_l - 2; i >= 0; i-- {
if nums[i] < nums[i+1] {
break
}
}
if i < 0 {
reverse(nums, 0, num_l-1)
return
}
t := nums[i]
var j int
for j = num_l-1; j > i; j-- {
if nums[j] > t {
break
}
}
nums[i], nums[j] = nums[j], t
reverse(nums, i+1, num_l-1)
}
func getPermutation(n int, k int) string {
ret := make([]byte, n)
for i := 0; i <n; i++ {
ret[i] = '1' + byte(i)
}
for k > 1 {
nextPermutation(ret)
k--
}
return string(ret)
}
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> sum(n, 1), index(n, 1);
string result;
for(int i = 1; i < n; i++)
{
sum[i] = sum[i-1]*i;
index[i] = i+1;
}
k--;
for(int i = n-1; i >=0; i--)
{
int pos = k/sum[i];
result += to_string(index[pos]);
index.erase(index.begin() + pos);
k = k%sum[i];
}
return result;
}
};
总结：
勤思考。
结语
不管怎么样好好加油。
