美文网首页
60.第k个序列

60.第k个序列

作者: HITZGD | 来源:发表于2018-11-12 20:27 被阅读0次

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

示例 1:
输入: n = 3, k = 3
输出: "213"

示例 2:
输入: n = 4, k = 9
输出: "2314"

思路
先通过举例来获得更好的理解。以n = 4,k = 9为例:

1234
1243
1324
1342
1423
1432
2134
2143
2314 <= k = 9
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

最高位可以取{1, 2, 3, 4},而每个数重复3! = 6次。所以第k=9个permutation的s[0]为{1, 2, 3, 4}中的第9/6+1 = 2个数字s[0] = 2。

而对于以2开头的6个数字而言,k = 9是其中的第k' = 9%(3!) = 3个。而剩下的数字{1, 3, 4}的重复周期为2! = 2次。所以s[1]为{1, 3, 4}中的第k'/(2!)+1 = 2个,即s[1] = 3。

对于以23开头的2个数字而言,k = 9是其中的第k'' = k'%(2!) = 1个。剩下的数字{1, 4}的重复周期为1! = 1次。所以s[2] = 1.

对于以231开头的一个数字而言,k = 9是其中的第k''' = k''/(1!)+1 = 1个。s[3] = 4

#include <vector>
using namespace std;
class Solution {
public:
    string getPermutation(int n, int k) {
        string result;
        string mun = "123456789";
        vector<int> factor(n, 1);
        for (int i = 1; i < n; i++) factor[i] = factor[i - 1] * i;
        k--;
        for (int i = n; i >= 1; i--)
        {
            int j = k / factor[i - 1];
            k %= factor[i - 1];
            result.push_back(mun[j]);
            mun.erase(mun.begin() + j);
        }
        return result;
    }
};

相关文章

  • 60.第k个序列

    题目给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 ...

  • LeetCode-Permutation Sequence

    目的:取第k个序列,见注解

  • 60.第k个排列

  • 60. 第k个排列

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

  • 60. 第k个排列

    给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n ...

  • 2018-01-29

    区间k大数查询 问题描述 给定一个序列,每次询问序列中第l个数到第r个数中第K大的数是哪个。 输入格式 第一行包含...

  • 60. Permutation Sequence/第k个排列

    The set [1,2,3,...,n] contains a total of n! unique permu...

  • 区间k大数查询

    问题描述给定一个序列,每次询问序列中第l个数到第r个数中第K大的数是哪个。 输入格式第一行包含一个数n,表示序列长...

  • Leetcode 数学类型总结

    7.整数反转 12.整数转罗马数字 13.罗马数字转整数 29.两数相除 50.Pow(x,y) 60.第k个排列...

  • Rotate Array 旋转序列

    Easy 序列含有n个元素,返回往右旋转k步的序列 For example若n = 7, k = 3,序列 [1,...

网友评论

      本文标题:60.第k个序列

      本文链接:https://www.haomeiwen.com/subject/kmqhfqtx.html