31. Next Permutation
題目是給定一個數字,要使用這個數字有使用到的數字,並透過排列組合,找到下一個排列組合比現在這個數字還大,可是卻是所有可行的排列組合中最小的,如果說現在的這個數字已經是排列組合中最大的數字,那我們就回傳排列組合中最小的數字。這個排列也可以稱做一種字典排列。
我的第一個直覺想法是,既然是排列組合題目,那我就把所有的排列組合窮舉出來,並且由小到大的排序,找出哪個數字和目前的數字相同,下一個數字就會是字典數了,當然如果是最大的數字,那就返回最小的數,題目還有要求要只在記憶體修改,那是這個並不是太困難的事情。
回溯法
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
sortedNums = sorted(nums)
res = []
def backtrack(curr, counter):
if len(curr) == len(sortedNums):
res.append(list(curr))
return
else:
for num in counter:
if counter[num] > 0:
counter[num] -= 1
curr.append(num)
backtrack(curr, counter)
counter[num] += 1
curr.pop()
backtrack([], Counter(sortedNums))
i = 0
while i < len(res):
if ''.join(map(str, res[i])) == ''.join(map(str, nums)):
break
i += 1
if i == len(res) - 1:
nums[::] = res[0]
else:
nums[::] = res[i+1]
但是我的做法時間複雜度非常高,會超時。
解法
這個解法只針對這個題目,不過因為這個題目是 Google 的高頻考題,所以我還是把這個題目放到了筆記之中。