关注Java领域相关技术 记录有趣的事情

LeetCode-60. 第k个排列

US-B.Ralph
US-B.Ralph
2020-09-05

问题地址

LeetCode每日一题/2020-09-05

LeetCode60. 第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"
输入: n = 4, k = 9
输出: "2314"

解析

解题思路

复杂度分析

数据操作分析

编码实现

官方解法

数学 + 缩小问题规模

思路:
  • 要想解决本题,首先需要了解一个简单的结论:
    • 对于 n 个不同的元素(例如数 1, 2, \cdots, n),它们可以组成的排列总数目为 n!
  • 对于给定的 n 和 k,我们不妨从左往右确定第 k 个排列中的每一个位置上的元素到底是什么。
  • 我们首先确定排列中的首个元素 a_1 。根据上述的结论,我们可以知道:
    • 以 1 为 a_1 的排列一共有 (n-1)! 个;
    • 以 2 为 a_1 的排列一共有 (n-1)! 个;
    • $\cdots$;
    • 以 n 为 a_1 的排列一共有 (n-1)! 个。
  • 由于我们需要求出从小到大的第 k 个排列,因此:
    • 如果 k \leq (n-1)!,我们就可以确定排列的首个元素为 1
    • 如果 (n-1)!<k \leq 2 · (n-1)! 我们就可以确定排列的首个元素为 2
    • $\cdots$
    • 如果 (n-1) \cdot (n-1)!<k \leq n \cdot (n-1)!,我们就可以确定排列的首个元素为 n;
    • 因此,第 k 个排列的首个元素就是:a_1 = \lfloor \frac{k-1}{(n-1)!} \rfloor + 1
      • 其中 \lfloor x \rfloor 表示将 x 向下取整。
  • 当我们确定了 a_1 后,如何使用相似的思路,确定下一个元素 a_2 呢?实际上,我们考虑以 a_1 为首个元素的所有排列:
    • [1,n] \backslash a_1 最小的元素为 a_2 的排列一共有 (n-2)! 个;
    • [1,n] \backslash a_1 次小的元素为 a_2 的排列一共有 (n-2)! 个;
    • $\cdots⋯$
    • [1,n] \backslash a_1 最大的元素为 a_2 的排列一共有 (n-2)! 个;
    • 其中 [1,n] \backslash a_1 表示包含 1, 2, \cdots n 中除去 a_1 以外元素的集合。这些排列从编号 (a_1-1) \cdot (n-1)! 开始,到 a_1 \cdot (n-1)! 结束,总计(n-1)! 个,因此第 k 个排列实际上就对应着这其中的第 k’ = (k-1) \bmod (n-1)! + 1 个排列。这样一来,我们就把原问题转化成了一个完全相同但规模减少 1 的子问题:
      • [1, n] \backslash a_1n−1 个元素组成的排列中,第 k’ 小的排列。

算法

  • 设第 k 个排列为 a_1, a_2, \cdots, a_n ,我们从左往右地确定每一个元素 a_i 。我们用数组 \textit{valid} 记录每一个元素是否被使用过。
  • 我们从小到大枚举 i:
    • 我们已经使用过了 i-1 个元素,剩余 n-i+1 个元素未使用过,每一个元素作为 a_i 都对应着 (n-i)! 个排列,总计 (n-i+1)! 个排列;
    • 因此在第 k 个排列中,a_i 即为剩余未使用过的元素中第 \lfloor \frac{k-1}{(n-i)!} \rfloor + 1 小的元素;
    • 在确定了 a_i 后,这 n-i+1 个元素的第 k 个排列,就等于 a_i 之后跟着剩余 n-i 个元素的第 (k-1) \bmod (n-i)! + 1 个排列。
  • 在实际的代码中,我们可以首先将 k 的值减少 1,这样可以减少运算,降低代码出错的概率。对应上述的后两步,即为:
    • 因此在第 k 个排列中,a_i 即为剩余未使用过的元素中第 \lfloor \frac{k}{(n-i)!} \rfloor + 1 小的元素;
    • 在确定了 a_i 后,这 n-i+1 个元素的第 k 个排列,就等于 a_i 之后跟着剩余 n-i 个元素的第 k \bmod (n-i)! 个排列。
  • 实际上,这相当于我们将所有的排列从 0 开始进行编号。
复杂度分析:
  1. 时间复杂度,O(n^2)
  2. 空间复杂度,O(N)
class Solution {
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; ++i) {
            factorial[i] = factorial[i - 1] * i;
        }

        --k;
        StringBuffer ans = new StringBuffer();
        int[] valid = new int[n + 1];
        Arrays.fill(valid, 1);
        for (int i = 1; i <= n; ++i) {
            int order = k / factorial[n - i] + 1;
            for (int j = 1; j <= n; ++j) {
                order -= valid[j];
                if (order == 0) {
                    ans.append(j);
                    valid[j] = 0;
                    break;
                }
            }
            k %= factorial[n - i];
        }
        return ans.toString();
    }
}
思考题

对于给定的排列 a_1, a_2, \cdots, a_n,你能求出 k 吗?

解答:

k = \left( \sum_{i=1}^n \textit{order}(a_i) \cdot (n-i)! \right) + 1

精彩评论

跳转地址:深度优先遍历 + 剪枝、有序数组模拟

思路

  • 一句话题解:以下给出了两种方法,思路其实是一样的:通过 计算剩余数字个数的阶乘数,一位一位选出第 k 个排列的数位。
思路分析
  • 容易想到,使用同「力扣」第 46 题: 全排列 的回溯搜索算法,依次得到全排列,输出第 kk 个全排列即可。事实上,我们不必求出所有的全排列。
  • 基于以下几点考虑:
    • 所求排列 一定在叶子结点处得到,进入每一个分支,可以根据已经选定的数的个数,进而计算还未选定的数的个数,然后计算阶乘,就知道这一个分支的 叶子结点 的个数:
      • 如果 k 大于这一个分支将要产生的叶子结点数,直接跳过这个分支,这个操作叫「剪枝」;
      • 如果 k 小于等于这一个分支将要产生的叶子结点数,那说明所求的全排列一定在这一个分支将要产生的叶子结点里,需要递归求解。

下面以示例 2:输入: n = 4,k = 9,介绍如何使用「回溯 + 剪枝」的思想得到输出 “2314”:

编码注意事项
  • 计算阶乘的时候,可以使用循环计算。注意:0!=1,它表示了没有数可选的时候,即表示到达叶子结点了,排列数只剩下 1 个;
  • 题目中说「给定 nn 的范围是 [1,9]」,可以把从 0 到 9 的阶乘计算好,放在一个数组里,可以根据索引直接获得阶乘值;
  • 编码的时候,+1 还是 −1 ,大于还是大于等于,这些不能靠猜。常见的做法是:代入一个具体的数值,认真调试。
方法一:回溯搜索算法 + 剪枝 ,直接来到叶子结点
  • 说明:
    • 这里感谢 @target-2 朋友提供的建议,在 dfs(index + 1, path); 后加上 return 剪枝更彻底;
    • @happycoder-3 将这一版代码改成了循环形式,更直接。大家可以参考 这里
  • 复杂度分析
    • 时间复杂度:O({N^2}),具体原因请见 @Jerry Tse 在本文下的回复;
    • 空间复杂度:O(N),nums、used、path 都与 N 等长,factorial 数组就 10 个数,是常数级别的。
  • 对于回溯算法(深度优先遍历)还比较陌生的朋友,可以参考我的题解 《回溯算法入门级详解 + 练习(持续更新)》

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;
        }
    }
}
  • k -= cnt; 这一步,每一次剪枝太慢,事实上,可以用除法加快这一步骤。但是需要维护一个有序数组(或者链表),时间复杂度不变。
方法二:有序数组(链表)模拟
  • 思路分析:以 n = 4,k = 6,为例,现在确定第 1 个数字填啥。如果第 k 个数恰好是后面的数字个数的阶乘,那么第 1 个数字就只能填最小的 1。

  • 如果 n = 4,k = 16,现在确定第 1 个数字填啥。如果 k 大于后面的数字个数的阶乘。数一数,可以跳过几个阶乘数。

  • 其实这个思路很像方法一的「剪枝」,只不过方法一就减法,方法二用除法。事实上,方法二要维护数组的有序性,所以时间复杂度不变。根据以上思路,设计算法流程如下:

  • 算法流程设计:
    • 把候选数放在一个 有序列表 里,从左到右根据「剩下的数的阶乘数」确定每一位填谁,公式 k / (后面几位的阶乘数) 的值 恰好等于候选数组的下标;
    • 选出一个数以后,k 就需要减去相应跳过的阶乘数的倍数;
    • 已经填好的数需要从候选列表里删除,注意保持列表的有序性(因为排列的定义是按照字典序);
    • 由于这里考虑的是下标,第 k 个数,下标为 k – 1,一开始的时候,k–。
  • 每次选出一个数,就将这个数从列表里面拿出。这个列表需要支持频繁的删除操作,因此使用双链表。在 Java 中 LinkedList 就是使用双链表实现的。

下面看算法是如何在示例 2 上工作的:

  • 复杂度分析
    • 时间复杂度:O({N^2}),N是数组长度;
    • 空间复杂度:$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();
    }
}
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

18 − 3 =