An Interest In:
Web News this Week
- April 2, 2024
- April 1, 2024
- March 31, 2024
- March 30, 2024
- March 29, 2024
- March 28, 2024
- March 27, 2024
June 16, 2022 01:30 pm GMT
Original Link: https://dev.to/theabbie/permutation-sequence-4ld2
Permutation Sequence
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))
Original Link: https://dev.to/theabbie/permutation-sequence-4ld2
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To