leetcode60-第k个排列

原题

给出集合 [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-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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月15日 22:01
下一篇 2020年5月16日 23:09

相关推荐

  • leetcode146-LRU缓存机制

    原题 运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。 获取数据 get(key) -…

    算法 2020年5月25日
    0100
  • leetcode274-H指数

    原题 https://leetcode.cn/problems/h-index/description 题解 核心是求数组中,大于等于h的数的个数 大于等于 h,个数的最大值。 核…

    算法 2024年3月18日
    050
  • leetcode200-岛屿数量

    原题 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水…

    算法 2019年11月24日
    0150
  • leetcode103-二叉树的锯齿形层次遍历

    原题 给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 例如:给定二叉树: [3,9,20,null,nul…

    算法 2020年1月25日
    060
  • leetcode543-二叉树的直径

    原题 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例: 给定二叉树 1 / \ 2 3 / \ 4 5…

    算法 2020年3月10日
    0210
  • leetcode297-二叉树的序列化与反序列化

    原题 序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。…

    算法 2020年1月15日
    0120
  • leetcode153-寻找旋转排序数组中的最小值

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,…

    算法 2020年1月3日
    080
  • leetcode46-全排列

    原题 给定一个没有重复数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [   [1,2,3],   [1,3,…

    算法 2020年3月3日
    0180
  • leetcode33-搜索旋转排序数组

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,…

    算法 2020年1月1日
    0160
  • leetcode141-环形链表

    原题 给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没…

    2019年12月14日
    0100

发表回复

登录后才能评论