Leetcode算法Java全解答--60. 第k个排列

超、凢脫俗 2022-04-05 08:58 176阅读 0赞

# Leetcode算法Java全解答–60. 第k个排列 #

### 文章目录 ###

*  Leetcode算法Java全解答--60. 第k个排列
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

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

## 想法 ##

k要先变成k-1，因为现在用的是下标值，是以0开头的，k–;

用k对(n-1)!取商，结果为数据 余数为下一个数字

比如n=4,这样排列出来的数据就有[1234,1243,1324,1342,1423,1432,2134,
    2143,2314,2341,2413,2431,3124...]
    
    第一轮：
    可以看到以1开头的有3*2*1 = 6种，同理2.3.4的都是这样
    这样8/6 = 1..2（商为1，余数为2）， 结果数据就是索引为1的2（第0个是1）
    然后把2从数组中移除
    
    第二轮
    这时候数据把2除外就有[134,143,314,341,413,431]
    可以看到以1开头的有2*1 = 2种，同理3.4的都是这样
    上一把余数是2，所以2/2 = 1..0，结果数据就是索引为1的3（第0个是1）
    
    第三轮
    这时候数据把2除外就有[14,41]
    可以看到以1开头的有1 =1种，同理4的都是这样
    上一把余数是0，所以0/1 = 0..1，结果数据就是索引为0的1（第0个是1）

## 结果 ##

超过99%的测试案例

时间复杂度/空间复杂度：n/n

## 总结 ##

k–那里没有想到

## 代码 ##

### 我的答案 ###

public String getPermutation(int n, int k) {
        if (n <= 1) {
            return "" + n;
        }
        ArrayList arrayList = new ArrayList();
        for (int i = 1; i <= n; i++) {
            arrayList.add(i);
        }
    
        StringBuilder result = new StringBuilder();
        int leaf = n;
        k = k - 1;
        while (leaf > 0) {
            // 循环求出(n-1)阶乘
            int val = 1;
            for (int i = 1; i <= leaf - 1; i++) {
                val = val * i;
            }
            // 求出下标索引index
            int index = k / val;
            result.append(arrayList.get(index));
            arrayList.remove(index);
            k = k % val;
            leaf--;
        }
        return result.toString();
    }

### 大佬们的答案 ###

public String better(int n, int k) {
            List<Integer> b = new ArrayList<>();
            int a[] = new int[n];
            int j = 0;
    
            for (int i = 0; i <= n; i++) {
                b.add(i);
            }
    
            for (int i = n; i > 0; i--) {
                if (k == 0) {
                    for (int g = b.size() - 1; g >= 1; g--) {
                        a[n - i - 1 + g] = b.get(b.size() - g);
                    }
                    break;
                }
                j = pa(i - 1);
                int l = k / j + 1;
                if (k % j != 0) {
                    a[n - i] = b.get(l);
                    b.remove(l);
                } else {
                    a[n - i] = b.get(l - 1);
                    b.remove(l - 1);
                }
                k = k % j;
    
            }
            String s = integerFormatString(a);
            return s;
        }
    
        private int pa(int n) {
            int k = 1;
            if (n == 0) {
                return 1;
            }
            for (int i = 1; i <= n; i++) {
                k = k * i;
            }
            return k;
        }
    
        public static String integerFormatString(int[] a) {
            int len = a.length;
            char[] ch = new char[len];
            for (int i = 0; i < len; i++) {
                switch (a[i]) {
                    case 0:
                        ch[i] = '0';
                        break;
                    case 1:
                        ch[i] = '1';
                        break;
                    case 2:
                        ch[i] = '2';
                        break;
                    case 3:
                        ch[i] = '3';
                        break;
                    case 4:
                        ch[i] = '4';
                        break;
                    case 5:
                        ch[i] = '5';
                        break;
                    case 6:
                        ch[i] = '6';
                        break;
                    case 7:
                        ch[i] = '7';
                        break;
                    case 8:
                        ch[i] = '8';
                        break;
                    case 9:
                        ch[i] = '9';
                        break;
                    default:
                        break;
                }
            }
            String str = new String(ch);
            return str;
        }

### 测试用例 ###

@Test
    public void test060() {
        // 创建测试案例
        int n1 = 3;
        int k1 = 3;
        int n2 = 3;
        int k2 = 6;
    
        // 测试案例期望值
        String expResult1 = "213";
        String expResult2 = "321";
    
    
        // 执行方法
        Solution060 solution060 = new Solution060();
        String result1 = solution060.getPermutation(n1,k1);
        String result2 = solution060.getPermutation(n2,k2);
    
        // 判断期望值与实际值
        Assert.assertEquals(expResult1, result1);
        Assert.assertEquals(expResult2, result2);
    
    }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan