Untitled
unknown
plain_text
a year ago
1.3 kB
8
Indexable
from collections import Counter class Solution: def isPermutationValid(self, permutation, frequencyMap): for num, value in Counter(permutation).items(): if num not in frequencyMap: return False if value != frequencyMap[num]: return False return True def moveByOne(self, nums: List[int], numToIndexMap, indexToNumMap) -> List[int]: position = len(nums) - 1 while position >= 0: num = nums[position] indexInMap = numToIndexMap[num] if indexInMap == len(numToIndexMap) - 1: nums[position] = indexToNumMap[0] position -= 1 else: nums[position] = indexToNumMap[indexInMap + 1] return def nextPermutation(self, nums: List[int]) -> None: frequencyMap = Counter(nums) numToIndexMap = {} indexToNumMap = {} uniqueElements = list(set(nums)) for index, num in enumerate(uniqueElements): numToIndexMap[num] = index indexToNumMap[index] = num self.moveByOne(nums, numToIndexMap, indexToNumMap) while not self.isPermutationValid(nums, frequencyMap): self.moveByOne(nums, numToIndexMap, indexToNumMap)
Editor is loading...
Leave a Comment