Leetcode--Permutation Sequence

Problem Description：

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

首先想到的暴力法，逐個(gè)的求排列，直到找到第k個(gè)排列，提交之后會(huì)超時(shí)，在網(wǎng)上搜索之后發(fā)現(xiàn)可以直接構(gòu)造出第k個(gè)排列，以n = 4，k = 17為例，數(shù)組src = [1,2,3,...,n]。

第17個(gè)排列的第一個(gè)數(shù)是什么呢：我們知道以某個(gè)數(shù)固定開(kāi)頭的排列個(gè)數(shù) = (n-1)! = 3! = 6, 即以1和2開(kāi)頭的排列總共6*2 = 12個(gè)，12 < 17, 因此第17個(gè)排列的第一個(gè)數(shù)不可能是1或者2，6*3 > 17, 因此第17個(gè)排列的第一個(gè)數(shù)是3。即第17個(gè)排列的第一個(gè)數(shù)是原數(shù)組（原數(shù)組遞增有序）的第m = upper(17/6) = 3（upper表示向上取整）個(gè)數(shù)。                                       

第一個(gè)數(shù)固定后，我們從src數(shù)組中刪除該數(shù)，那么就相當(dāng)于在當(dāng)前src的基礎(chǔ)上求第k - (m-1)*(n-1)! = 17 - 2*6 = 5個(gè)排列，因此可以遞歸的求解該問(wèn)題。

代碼實(shí)現(xiàn)中注意一個(gè)小細(xì)節(jié)，就是一開(kāi)始把k--，目的是讓下標(biāo)從0開(kāi)始，這樣下標(biāo)就是從0到n-1，不用考慮n時(shí)去取余，更好地跟數(shù)組下標(biāo)匹配。具體代碼如下：

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)