成都网站建设设计

将想法与焦点和您一起共享

C++如何实现序列排序

这篇文章主要讲解了“C++如何实现序列排序”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C++如何实现序列排序”吧!

创新互联公司致力于成都网站制作、网站建设,成都网站设计,集团网站建设等服务标准化,推过标准化降低中小企业的建站的成本,并持续提升建站的定制化服务水平进行质量交付,让企业网站从市场竞争中脱颖而出。 选择创新互联公司,就选择了安全、稳定、美观的网站建设服务!

Permutation Sequence 序列排序

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

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

  1. "123"

  2. "132"

  3. "213"

  4. "231"

  5. "312"

  6. "321"

Given n and k, return the kth permutation sequence.

Note:

  • Given n will be between 1 and 9 inclusive.

  • Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

这道题是让求出n个数字的第k个排列组合,由于其特殊性,我们不用将所有的排列组合的情况都求出来,然后返回其第k个,这里可以只求出第k个排列组合即可,那么难点就在于如何知道数字的排列顺序,首先要知道当 n = 3 时,其排列组合共有 3! = 6 种,当 n = 4 时,其排列组合共有 4! = 24 种,这里就以 n = 4, k = 17 的情况来分析,所有排列组合情况如下:

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

可以发现,每一位上 1,2,3,4 分别都出现了6次,当最高位上的数字确定了,第二高位每个数字都出现了2次,当第二高位也确定了,第三高位上的数字都只出现了1次,当第三高位确定了,那么第四高位上的数字也只能出现一次,下面来看 k = 17 这种情况的每位数字如何确定,由于 k = 17 是转化为数组下标为 16:

最高位可取 1,2,3,4 中的一个,每个数字出现 3!= 6 次(因为当最高位确定了,后面三位可以任意排列,所以是 3!,那么最高位的数字就会重复 3!次),所以 k = 16 的第一位数字的下标为 16 / 6 = 2,在 "1234" 中即3被取出。这里的k是要求的坐标为k的全排列序列,定义 k" 为当最高位确定后,要求的全排序列在新范围中的位置,同理,k"" 为当第二高为确定后,所要求的全排列序列在新范围中的位置,以此类推,下面来具体看看:

第二位此时从 1,2,4 中取一个,k = 16,则此时的 k" = 16 % (3!) = 4,注意思考这里为何要取余,如果对这 24 个数以6个一组来分,那么 k=16 这个位置就是在第三组(k/6 = 2)中的第五个(k%6 = 4)数字。如下所示,而剩下的每个数字出现 2!= 2 次,所以第二数字的下标为 4 / 2 = 2,在 "124" 中即4被取出。

3124
3142
3214
3241
3412 <--- k" = 4
3421

第三位此时从 1,2 中去一个,k" = 4,则此时的 k"" = 4 % (2!) = 0,如下所示,而剩下的每个数字出现 1!= 1 次,所以第三个数字的下标为 0 / 1 = 0,在 "12" 中即1被取出。

3412 <--- k"" = 0
3421

第四位是从2中取一个,k"" = 0,则此时的 k""" = 0 % (1!) = 0,如下所示,而剩下的每个数字出现 0!= 1 次,所以第四个数字的下标为 0 / 1= 0,在 "2" 中即2被取出。

3412 <--- k""" = 0

那么就可以找出规律了
a1 = k / (n - 1)!
k1 = k

a2 = k1 / (n - 2)!
k2 = k1 % (n - 2)!
...

an-1 = kn-2 / 1!
kn-1 = kn-2 % 1!

an = kn-1 / 0!
kn = kn-1 % 0!

代码如下:

class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        string num = "123456789";
        vector f(n, 1);
        for (int i = 1; i < n; ++i) f[i] = f[i - 1] * i;
        --k;
        for (int i = n; i >= 1; --i) {
            int j = k / f[i - 1];
            k %= f[i - 1];
            res.push_back(num[j]);
            num.erase(j, 1);
        }
        return res;
    }
};

感谢各位的阅读,以上就是“C++如何实现序列排序”的内容了,经过本文的学习后,相信大家对C++如何实现序列排序这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!


网页名称:C++如何实现序列排序
当前地址:http://chengdu.cdxwcx.cn/article/ipjpse.html