Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

第K个排列

Posted on Edited on In , ,
Symbols count in article: 4k Reading time ≈ 4 mins.

来源Leetcode第60题第K个排列

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

按大小顺序列出所有排列情况，并一一标记，
给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:

输入: n = 3, k = 3
输出: “213”

TLE代码

按照之前全排列的代码，改了一下，但是由于生成的列表是无序的，因而我采取了将其排序的操作，但是这样的最后导致了超时。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public List<List<Integer>> ans = new ArrayList<>();

private void nextPer(int[] arr,int start){
    //当start==arr.length-1时，说明子序列的长度为1，就不用再往下分子序列了
    if(start==arr.length-1){
        List<Integer> temp_ans = new ArrayList<>();
        for(int i = 0 ; i < arr.length ; i++){
            temp_ans.add(arr[i]);
        }
        //System.out.println(temp_ans);
        ans.add(temp_ans);
        return ;
    }
    for(int i=start;i<arr.length;i++){
        //start代表的是每一个子序列的第一个位置，我们每一层递归的任务都只有一个：
        //枚举该层子序列第一个位置可以取的值
        int temp=arr[start];
        arr[start]=arr[i];
        arr[i]=temp;

        //该层递归的子序列第一个位置已经确定了，所以又可以往下再分
        nextPer(arr,start+1);

        //把第该层子序列第一个位置的值换成另外一个值，所以要交换回来
        temp=arr[start];
        arr[start]=arr[i];
        arr[i]=temp;
    }
}

public void sort(List<List<Integer>> ans){
    for(int i = 0 ; i < ans.size() ; i ++ ){
        for(int j = i  + 1; j < ans.size() ; j++){
            for(int k = 0; k < ans.get(j).size(); k ++){
                if(ans.get(i).get(k) < ans.get(j).get(k)){
                    break;
                }
                if(ans.get(i).get(k) > ans.get(j).get(k)){
                    //System.out.println(k + " " + ans.get(i).get(k) + " " + ans.get(j).get(k));
                    List<Integer> temp = ans.get(i);
                    ans.set(i,ans.get(j));
                    ans.set(j,temp);
                    break;
                }
            }
        }
    }
}

public String getPermutation(int n, int k) {
    int [] nums = new int[n];
    for(int i = 1 ; i <= n ; i++)
        nums[i - 1] = i;
    nextPer(nums,0);
    sort(ans);
    String result = "";
    for(int i = 0 ; i < n ; i ++ ){
        result += ans.get(k - 1).get(i);
    }
    //System.out.println(result);
    return result;
}

找规律

思路来源题解

假设n=5,k=35,
n为5的全排列就是首位为1-5的如下排列的所有
1_,,,2,,,3,,,4,,,5,,,每个各有24个排列，组成12345的全排列
由于k=35<48,也就是说第35个肯定在首位为2的全排列里边,所以第一个取2。
接下来就是考虑剩下1345这四个数的全排列里边取第k=35-24=11个，
1,,3,,4,,5,,每个各有6个排列，组成1345的全排列，
由于k=11<12,也就是说第11个肯定在首位为3的全排列里边，所以第二个数取3
接下来就是考虑剩下145这三个数的全排列里边取第k=11-6=5个，
1,4,5,_每个各有2个排列，组成145的全排列
由于k=5<6,也就是说第5个肯定在首位为5的全排列里边，所以第三个数取5
接下来就是考虑剩下14这两个数的排列里边取第k=5-4=1个
1_4_每个各有1个排列，组成14的排列，
由于k=1,所以第四个数取1
最后加上剩下的最后一个4，结果就是23514
结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    String getPermutation(int n, int k)
    {
        StringBuilder nums = new StringBuilder();
        int factor[] = {1,1,2,6,24,120,720,5040,40320,362880};
        for (int i = 1;i <= n;++i)
            nums.append(i);
        String answer = "";
        int interval,loop_times = n;
        for (int i = 0;i < loop_times;++i)
        {
            --n;
            interval = (k - 1) / factor[n];
            answer += nums.charAt(interval);
            nums = nums.deleteCharAt(interval);
            k = k - interval * factor[n];
        }
        return answer;
    }
}

回溯 + 剪枝

来自题解

大致思路其实是同上者

  • 我们知道所求排列一定在叶子结点处得到。事实上，进入每一个分支的时候，我们都可以通过递归的层数，直接计算这一分支可以得到的叶子结点的个数。

这是因为：进入一个分支的时候，我们可以根据已经选定的数的个数，进而确定还未选定的数的个数，然后计算阶乘，就知道这一个分支的叶子结点有多少个。

  • 2、如果 k 大于这一个分支将要产生的叶子结点数，直接跳过这个分支，即“剪枝”即可。

  • 这是因为：即使你回溯去做，要设置状态，回溯回来的时候状态还要重置，但其实跳过的这个分支的叶子结点具体是啥我们并不关心。

  • 3、如果 k 小于等于这一个分支将要产生的叶子结点数，那说明所求的全排列一定在这一个分支将要产生的叶子结点里，需要递归求解。

  • 4、计算阶乘的时候，你可以使用循环计算，特别注意：0!=1，它表示了没有数可选的时候，即表示到达叶子结点了，排列数只剩下 1 个。

  • 又因为题目中说“给定 nn 的范围是 [1,9]”，故可以实现把从 0 到 9 的阶乘计算好，放在一个数组里，可以根据索引直接获得阶乘值，见文后“代码 2”。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public String getPermutation(int n, int k) {
        int[] nums = new int[n];
        boolean[] used = new boolean[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
            used[i] = false;
        }
        int[] factorial = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
        List<String> pre = new ArrayList<>();
        return dfs(nums, used, n, k, 0, pre, factorial);
    }

    private String dfs(int[] nums, boolean[] used, int n, int k, int depth, List<String> pre, int[] factorial) {
        if (depth == n) {
            StringBuilder sb = new StringBuilder();
            for (String c : pre) {
                sb.append(c);
            }
            return sb.toString();
        }
        int ps = factorial[n - 1 - depth];
        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
			//确定递归层数的位置
            if (ps < k) {
                k -= ps;
                continue;
            }
            pre.add(nums[i] + "");
            used[i] = true;
            return dfs(nums, used, n, k, depth + 1, pre, factorial);
        }
        // 如果参数正确的话，代码不会走到这里
        throw new RuntimeException("参数错误");
    }
}