[Leetcode][第60题][JAVA][第k个排列][回溯][DFS][剪枝]

忘是亡心i 2022-12-04 02:27 156阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

###### 1. 回溯搜索算法 + 剪枝 ，直接来到叶子结点 ######

![在这里插入图片描述][20200905153653979.png_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]

**时间复杂度：O(N^2) 空间复杂度：O(N)**  
![在这里插入图片描述][20200905153806396.png_pic_center]

import java.util.Arrays;
    
    public class Solution { 
    
        /** * 记录数字是否使用过 */
        private boolean[] used;
    
        /** * 阶乘数组 */
        private int[] factorial;
    
        private int n;
        private int k;
    
        public String getPermutation(int n, int k) { 
            this.n = n;
            this.k = k;
            calculateFactorial(n);
    
            // 查找全排列需要的布尔数组
            used = new boolean[n + 1];
            Arrays.fill(used, false);
    
            StringBuilder path = new StringBuilder();
            dfs(0, path);
            return path.toString();
        }
    
    
        /** * @param index 在这一步之前已经选择了几个数字，其值恰好等于这一步需要确定的下标位置 * @param path */
        private void dfs(int index, StringBuilder path) { 
            if (index == n) { 
                return;
            }
    
            // 计算还未确定的数字的全排列的个数，第 1 次进入的时候是 n - 1
            int cnt = factorial[n - 1 - index];
            for (int i = 1; i <= n; i++) { 
                if (used[i]) { 
                    continue;
                }
                if (cnt < k) { 
                    k -= cnt;
                    continue;
                }
                path.append(i);
                used[i] = true;
                dfs(index + 1, path);
                // 注意 1：没有回溯（状态重置）的必要
    
                // 注意 2：这里要加 return，后面的数没有必要遍历去尝试了
                return;
            }
        }
    
        /** * 计算阶乘数组 * * @param n */
        private void calculateFactorial(int n) { 
            factorial = new int[n + 1];
            factorial[0] = 1;
            for (int i = 1; i <= n; i++) { 
                factorial[i] = factorial[i - 1] * i;
            }
        }
    }
    
    作者：liweiwei1419
    链接：https://leetcode-cn.com/problems/permutation-sequence/solution/hui-su-jian-zhi-python-dai-ma-java-dai-ma-by-liwei/

###### 2. 有序数组（链表）模拟 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 8]

**时间复杂度：O(N2) 空间复杂度：O(N)**

import java.util.LinkedList;
    import java.util.List;
    
    public class Solution { 
    
        public String getPermutation(int n, int k) { 
            // 注意：相当于在 n 个数字的全排列中找到下标为 k - 1 的那个数，因此 k 先减 1
            k --;
    
            int[] factorial = new int[n];
            factorial[0] = 1;
            // 先算出所有的阶乘值
            for (int i = 1; i < n; i++) { 
                factorial[i] = factorial[i - 1] * i;
            }
    
            // 这里使用数组或者链表都行
            List<Integer> nums = new LinkedList<>();
            for (int i = 1; i <= n; i++) { 
                nums.add(i);
            }
    
            StringBuilder stringBuilder = new StringBuilder();
    
            // i 表示剩余的数字个数，初始化为 n - 1
            for (int i = n - 1; i >= 0; i--) { 
                int index = k / factorial[i] ;
                stringBuilder.append(nums.remove(index));
                k -= index * factorial[i];
            }
            return stringBuilder.toString();
        }
    }
    
    作者：liweiwei1419
    链接：https://leetcode-cn.com/problems/permutation-sequence/solution/hui-su-jian-zhi-python-dai-ma-java-dai-ma-by-liwei/

#### 【总结】 ####

###### 1. 剪枝大法好 充分利用条件边界 减少回溯 ######

###### 2.回溯思想 ######

[【数据结构与算法】【算法思想】回溯算法][Link 1]

###### 3.常规思路超时 全排列 dfs传递的是深度 不是具体某一个值 ######

**相关题目**  
[\[Leedcode\]\[JAVA\]\[第46题\]\[全排列\]\[回溯算法\]][Leedcode_JAVA_46]

class Solution { 
        private static String str = "";
        public String getPermutation(int n, int k) { 
            List<String> a =new ArrayList<String>();
            boolean[] used = new  boolean[n];
            int[]num = new int[n];
            for(int i =0 ;i<n;i++){ 
                num[i] = i+1;
            }
            
            permunte(0,n,num,a,used,k,"");
               
    
            return str;
        }
    
    
         private void permunte(int depth, int n,int[] num, List<String> a,boolean[] used ,int  k,String s){ 
             if(s.length() == n){ 
                 a.add(s);
                 if(a.size() == k){ 
                     str = s;
                    return ;
                }
             }
            
             
    
               for(int i=0;i<n;i++){ 
                    StringBuffer sb = new StringBuffer(s);
                        if(!used[i]){ 
                            used[i] = true;
                            sb.append(num[i]);
                            permunte(depth+1,n,num,a,used,k,sb.toString());
                            used[i] = false;
                            sb.deleteCharAt(sb.length()-1);
                        }
                       
                }
    
         }
     
    }

转载链接：https://leetcode-cn.com/problems/permutation-sequence/solution/hui-su-jian-zhi-python-dai-ma-java-dai-ma-by-liwei/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/966eecabf9664737840612d33e2550e9.png
[20200905153653979.png_pic_center]: /images/20221123/1defe2e7b38441baa2dd4675f2a1027e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/ac366cded1a94cdf92a1f4f24761b6eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/33b1fd26afe44a139716bb44264abddf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/ddcd5a007bd342d084b51f1aca5eb602.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/07baf5585a124d6089be2f9a2b459f5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/c0d5a94ddaa14edcab9f4ed5ddf8fb13.png
[20200905153806396.png_pic_center]: /images/20221123/6de072ba10424e5fad9aca8340bad3eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/ab833aa54ca642509fd6ab3ea41cb408.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/75fe794aa7f54871ae0d037072eb9f1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/fe871e9ed51547f9a84485706042c0c9.png
[Link 1]: https://blog.csdn.net/dadongwudi/article/details/108242926
[Leedcode_JAVA_46]: https://blog.csdn.net/dadongwudi/article/details/105760561