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 for n = 3:
-
"123" -
"132" -
"213" -
"231" -
"312" -
"321"
Given n and k, return the kth permutation sequence.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
Example 3:
Input: n = 3, k = 1
Output: "123"
Constraints:
-
1 <= n <= 9 -
1 <= k <= n!
SOLUTION:
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
n = len(nums)
i = n - 1
while i > 0:
if nums[i - 1] < nums[i]:
break
i -= 1
if i == 0:
nums.reverse()
return
mdiff = float('inf')
closest = None
for j in range(i, n):
if nums[j] > nums[i - 1] and nums[j] - nums[i - 1] <= mdiff:
mdiff = nums[j] - nums[i - 1]
closest = j
if closest:
nums[i - 1], nums[closest] = nums[closest], nums[i - 1]
for j in range(i, (i + n) // 2):
nums[j], nums[n - j + i - 1] = nums[n - j + i - 1], nums[j]
def getPermutation(self, n: int, k: int) -> str:
nums = list(range(1, n + 1))
for _ in range(k - 1):
self.nextPermutation(nums)
return "".join(map(str, nums))
Top comments (0)