☆打卡算法☆LeetCode 60、排列序列 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定n和k，返回第k个排列。”

题目链接：

来源：力扣（LeetCode）

链接：60. 排列序列 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

“123”
“132”
“213”
“231”
“312”
“321”

给定 n 和 k，返回第 k 个排列。

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

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

二、解题

1、思路分析

这个题对于给定的n和k，需要知道从左往右第k个排列中的每个位置的元素是什么。

首先求出第k个排列的首个元素，然后向下取整。

根据相似的思路，确定下一个元素。

2、代码实现

代码参考：

public class Solution {
    public int[] factor = new int[]{1,1,2,6,24,120,720,5040,40320,362880};
    public string GetPermutation(int n, int k) {
        StringBuilder path = new StringBuilder();
        bool[] visited = new bool[n + 1];
        dfs(n, k, 0, visited, path);
        return path.ToString();
    }

    private void dfs(int n, int k, int depth, bool[] visited, StringBuilder path){
        if(depth == n){
            return;
        }

        int fac = factor[n - 1 - depth];
        for(int i = 1; i <= n; i++){
            if(visited[i] == false){
                //当k大于可生成的叶子节点数，剪枝
                if(k > fac){
                    k -= fac;
                    continue;
                }
                path.Append(i.ToString());
                visited[i] = true;
                dfs(n, k, depth+1, visited, path);
                return;
            }
        }
    }
}

3、时间复杂度

时间复杂度 ： O(n²)

其中n是数组的长度，只需要遍历一遍数组即可求得答案。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

不要回溯，容易超时，可以通过数学的方法解决，其实就是不断缩小范围。