60.第k个排列

题目

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

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

"123"

"132"

"213"

"231"

"312"

"321"

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

说明:

给定 n 的范围是 [1, 9]。

给定 k 的范围是[1, n!]。

示例 1:

示例 2:

题解

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

从小到大把数排好;

用backtrack的方法遍历,每次遍历到一个全排列那么结果,count+1;

遍历到n就return输出

由于用的是backtrack,后面 count > k的情况都直接return掉;

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

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

后来这个版本提交的时候我以为可以洗洗睡啦.

结果,卧槽,居然换一种语言就超时啦~~

TLE

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

人生苦短,我用python

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

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

那哪些步骤可以跳过呢.

4的全排列是:

1 + 全排列

2 + 全排列

3 + 全排列

4 + 全排列

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

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

1 + 全排列(3!个)

2 + 全排列(3!个)

3 + 全排列(3!个)

4 + 全排列(3!个)

这就很好了呀~

具体来说是:

n 个数字有 n!种全排列,每种数字开头的全排列有 (n - 1)!种。

所以用 k / (n - 1)! 就可以得到第 k 个全排列是以第几个数字开头的。

用 k % (n - 1)! 就可以得到第 k 个全排列是某个数字开头的全排列中的第几个。

数学之美啊,有木有。

然后就快速实现了python的code AC了.

每日英文

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民法

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180906A0B9XZ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券