文档章节

求第k个全排列 Permutation Sequence

叶枫啦啦
 叶枫啦啦
发布于 2017/09/06 10:40
字数 889
阅读 11
收藏 0

问题:

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 (ie, 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.

解决:

① 题目要求求出n个数的全排列中第k个排列,题目只要求求出第k种情况,因此没必要track所有的排列状态导致浪费空间,并且这种算法会超时。

http://www.cnblogs.com/grandyang/p/4358678.html

首先我们要知道当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次,所以k = 16的第一位数字的下标为16 / 6 = 2,{1,2,3,4} —>即3被取出。
  • 第二位此时从1,2,4中取一个,k = 16时此时的k' = 16 % (3!) = 4,而剩下的每个数字出现2!= 2次,所以第二数字的下标为4 / 2 = 2,{1,2,4} —>即4被取出。
  • 第三位此时从1,2中去一个,k' = 4是此时的k'' = 4 % (2!) = 0,而剩下的每个数字出现1!= 1次,所以第三个数字的下标为 0 / 1 = 0,{1,2} -->即1被取出。
  • 第四位是从2中取一个,k'' = 0是此时的k''' = 0 % (1!) = 0,而剩下的每个数字出现0!= 1次,所以第四个数字的下标为0 / 1= 0,{2} --> 即2被取出。

那么我们就可以找出规律了

a1 = k / (n - 1)!

k1 = k % (n - 1)!

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 { //15ms
    public String getPermutation(int n, int k) {
        if(n <= 0) return "";
        k --;//让下标从0开始目的是让下标从0开始,这样下标就是从0到n-1,不用考虑n时去取余,更好地跟数组下标匹配。
        StringBuilder sb = new StringBuilder();
        int factorial = 1;
        List<Integer> nums = new ArrayList<>();//用于保存排列数
        for (int i = 2;i < n ;i ++ ) {//求出n - 1的阶乘
            factorial *= i;
        }
        for (int i = 1;i <= n ;i ++ ) {
            nums.add(i);
        }
        int round = n - 1;//记录取出的次数
        while(round >= 0){
            int index = k / factorial;
            k %= factorial;
            sb.append(nums.get(index));
            nums.remove(index);
            if(round > 0){
                factorial /= round;
            }
            round --;
        }
        return sb.toString();
    }
}

② 在discuss中看到的,使用数组保存n个数字。

class Solution {//15ms
    public String getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) {
            return "";
        }
        int[] nums = new int[n];
        int factorial = 1;
        for (int i = 1; i <= n; i ++) {
            nums[i-1] = i;//要排列的数
            factorial *= i;//n!
        }
        -- k;//下标从0开始
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i ++) {
            factorial = factorial / (n - i);
            int s = k / factorial;
            sb.append(nums[s]);
            for (int j = s; j < n-i-1; ++j) {//移除已经选中的数字
                nums[j] = nums[j + 1];   
            }
            k = k % factorial;
        }
        return sb.toString();
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 13
博文 577
码字总数 384162
作品 0
海淀
私信 提问

暂无文章

ngrok 外网映射工具

ngrok介绍 许多刚学java web的同学(包括我自己)肯定都非常好奇,如何在外网上访问自己做的项目,跟我们本地访问tomcat有什么区别? 今天就向大家介绍一个非常强大的外网映射工具:ngrok.ngrok可以...

edison_kwok
41分钟前
2
0
Spark Streaming的优化之路——从Receiver到Direct模式

          作者:个推数据研发工程师 学长 1 业务背景 随着大数据的快速发展,业务场景越来越复杂,离线式的批处理框架MapReduce已经不能满足业务,大量的场景需要实时的数据处理结果来...

个推
今天
4
0
壮丽70年·奋斗新时代|蒸妙集团熏蒸中会阴熏蒸的神奇好处

聚结相合之处为会。会阴居两阴间,为督、任、冲三脉的起点,三脉背出两阴之间,会聚阴部,因名会阴。会阴,经穴名。出《针灸甲乙经》。会阴别名屏翳、下极、金门。属任脉。在会阴部,男性当阴...

公益传承
今天
2
0
pentaho-kettle-8.2.0.0-R源码开发环境搭建

1.从Kettle官网下载源码,本文使用的是pentaho-kettle-8.2.0.0-R 下载地址:https://codeload.github.com/pentaho/pentaho-kettle/zip/8.2.0.0-R 2.打开eclipse,选择一个新的工作空间,然后设...

gq_2010
今天
1
0
lua web快速开发指南(7) - 高效的接口调用 - httpc库

httpc库基于cf框架都内部实现的socket编写的http client库. httpc库内置SSL支持, 在不使用代理的情况下就可以请求第三方接口. httpc支持header、args、body、timeout请求设置, 完美支持各种h...

水果糖的小铺子
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部