【Leetcode】60. 第k个排列

题目

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

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

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321" 给定 n 和 k,返回第 k 个排列。

说明:

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

输入: n = 3, k = 3
输出: "213"

示例 2:

输入: n = 4, k = 9
输出: "2314"

题解

这道题还蛮有意思的,我首先一看,这不是backtrack的经典题目吗? backtrack的剪枝可以参看相关文章中有详细的step-by-step的流程.

  1. 从小到大把数排好;
  2. 用backtrack的方法遍历,每次遍历到一个全排列那么结果,count+1;
  3. 遍历到n就return输出
  4. 由于用的是backtrack,后面 count > k的情况都直接return掉;

然后用java写了一个版本,还没有剪枝就ac啦.

class Solution {
int count = 0;
    List<Integer> finalRes;
    public String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        //第几个解.
        List<Integer> resTemp = new ArrayList<>();
        boolean[] haveSeen = new boolean[n];
        backtrack(nums, k, resTemp, haveSeen);
        StringBuilder res = new StringBuilder();
        for (Integer i : finalRes) {
            res.append(i);
        }
        return res.toString();
    }

    public void backtrack(int[] nums, int k, List<Integer> tempIndex, boolean[] haveSeen) {
        if (tempIndex.size() == nums.length) {
            count++;
        }
        if (count == k && tempIndex.size() == nums.length) {
            finalRes = new ArrayList<>(tempIndex);
            return;
        } else if (count < k && tempIndex.size() == nums.length) {
            tempIndex = new ArrayList<>();
        }
        for (int i = 0; i < nums.length; i++) {
            if (haveSeen[i]) {
                continue;
            }
            tempIndex.add(nums[i]);
            haveSeen[i] = true;
            backtrack(nums, k, tempIndex, haveSeen);
            haveSeen[i] = false;
            tempIndex.remove(tempIndex.size() - 1);
        }
    }
}

由于前几天后台有同学反馈,希望给出java版本的题解。所以又动手写了一个python版本.

class Solution:
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        global count
        global finalRes
        count = 0
        finalRes = []

        def backtrack(nums, k, resTemp, haveSeen):
            global count
            global finalRes
            if count > k:
                return
            if len(resTemp) == len(nums):
                count += 1
            if count == k and len(resTemp) == len(nums):
                finalRes = [str(_) for _ in resTemp]
                return
            elif count < k and len(resTemp) == len(nums):
                resTemp = []
            for i in range(0, len(nums)):
                if count > k:
                    break
                if haveSeen[i]:
                    continue
                resTemp.append(nums[i])
                haveSeen[i] = True
                backtrack(nums, k, resTemp, haveSeen)
                haveSeen[i] = False
                resTemp.pop()

        backtrack([_ + 1 for _ in range(0, n)], k, [], [False for _ in range(0, n)])
        return "".join(finalRes)

后来这个版本提交的时候我以为可以洗洗睡啦. 结果,卧槽,居然换一种语言就超时啦~~

TLE

这倒是个意外.难道我的python写的有性能问题,不应该啊,不是:

人生苦短,我用python

我就继续想剪枝,还能怎么剪枝?

剪枝是啥,不就是跳过某些步骤吗?

那哪些步骤可以跳过呢.

4的全排列是: 1 + {2,3,4}全排列 2 + {1,3,4}全排列 3 + {1,2,4}全排列 4 + {1,2,3}全排列

似乎可以转化成子问题啊.

由于题目只要求出第几个,我们再看看个数的规律

1 + {2,3,4}全排列(3!个) 2 + {1,3,4}全排列(3!个) 3 + {1,2,4}全排列(3!个) 4 + {1,2,3}全排列(3!个)

这就很好了呀~

具体来说是:

  • n 个数字有 n!种全排列,每种数字开头的全排列有 (n - 1)!种。
  • 所以用 k / (n - 1)! 就可以得到第 k 个全排列是以第几个数字开头的。
  • 用 k % (n - 1)! 就可以得到第 k 个全排列是某个数字开头的全排列中的第几个。 数学之美啊,有木有。 然后就快速实现了python的code AC了.
class Solution:
    def getPermutation(self, n, k):
        nums = [str(_ + 1) for _ in range(0, n)]
        if k == 1:
            return "".join(nums)

        fact = 1
        for i in range(2, n):
            fact *= i

        round = n - 1
        k -= 1
        finalRes = []
        while round >= 0:
            index = int(k / fact)
            k %= fact
            finalRes.append(nums[index])
            nums.remove(nums[index])
            if round > 0:
                fact /= round
            round -= 1
        return "".join(finalRes)

每日英文

  • pulicity (n.) 曝光度,知名度
    • enhanace the ~ of yourself 提高自己的知名度
  • publication (n.) 刊物,发表
  • Publicize (v.) 宣传
    • issue (v.) 发表
  • People's Republic Of China
  • in public
  • Republicans (n.)共和主义者
  • mass (n.)群众 (v.)聚集 (a.集中的)
    • masses of = many
  • civilian (a.)平民
    • civil law 民法

原文发布于微信公众号 - Leetcode名企之路(DailyLeetCode)

原文发表时间:2018-09-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据风控

Python中如何进行数据分组

数据分组 根据数据分析对象的特征,按照一定的数值指标,把数据分析对象划分为不同的区间进行研究,以揭示其内在联系和规律性。 cut 函数: cut(series,...

36970
来自专栏java一日一条

最快最简单的排序算法:桶排序

在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总...

11310
来自专栏mySoul

设计模式-UML关系基础

12250
来自专栏ml

向前字典排序

          next_permutation算法对区间元素进行一次组合排序,使之字典顺序大于原来的排序,有如下两个使用原形,对迭代器区间[first,l...

27990
来自专栏海天一树

小朋友学C语言(4):单精度浮点数与双精度浮点数

上节课 简单介绍了浮点数。计算机程序中的浮点数分为单精度浮点数和双精度浮点数。 单精度和双精度精确的范围不一样。 计算机里的最基本的存储单位用位(bit)来表...

406120
来自专栏mathor

BFPRT算法

 首先将原数组分成5个一组,每组内进行排序,组间不排序,然后将每组的中位数取出再次进行上述操作,直到最后只能分成一组了,然后取出中位数,将这个中位数当作标尺进行...

11420
来自专栏前端说吧

JS-用js的for循环实现九九乘法表以及其他算数题等

54960
来自专栏TensorFlow从0到N

讨厌算法的程序员 1 - 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生...

34540
来自专栏人工智能LeadAI

讨厌算法的程序员 1 | 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生出一...

30670
来自专栏我是攻城师

使用位运算替代模运算

35250

扫码关注云+社区

领取腾讯云代金券