https://leetcode-cn.com/problems/next-permutation/
# -*- coding:utf-8 -*- class Solution: def nextPermutation(self, nums): """ Do not return anything, modify nums in-place instead. """ firstIndex = -1 n = len(nums) def reverse(nums, i, j): """ 翻转列表 :param nums: :param i: :param j: :return: """ while i < j: nums[i], nums[j] = nums[j], nums[i] i += 1 j -= 1 # 正序查找 for i in range(n - 2, -1, -1): if nums[i] < nums[i + 1]: firstIndex = i break # 查找不到直接翻转返回 if firstIndex == -1: reverse(nums, 0, n - 1) return nums # 翻转查找 secondIndex = -1 for i in range(n - 1, firstIndex, -1): if nums[i] > nums[firstIndex]: secondIndex = i break # 交换两次查找的索引 nums[firstIndex], nums[secondIndex] = nums[secondIndex], nums[firstIndex] # 翻转回来返回 reverse(nums, firstIndex + 1, n - 1) return nums if __name__ == '__main__': nums = [1, 2, 3] print(Solution().nextPermutation(nums))
思路:这道题,不得不说太巧了,太棒了,学到了很多。
这道题就是找比当前大的字典序,这道题的思路比较巧。
举个例子:[1,2,4,6,5,2,1]
首先从后向前找能够将当前字典序变大的位置,之所以是从后向前找,是因为要找对字典序影响最小的元素。我们找到了4,4之后的元素都是降序,也就是说对于4之后的元素,已经满足了最大字典序。
然后我们找到了影响字典序的罪魁祸首4,就要找他和谁交换呢?因为我们希望字典序的增加比较小,因此我们继续在4后倒序找比4大的数,因为4后已经满足降序,因此倒序找到比4大的数就是最小的数,也就是能影响字典序最小的数字5。
我们将4和5交换,此时列表变成 [1,2,5,6,4,2,1]
这时候5后依然保持着最大字典序的状态,我们将其翻转,到最小字典序。 [1,2,5,1,2,4,6]
这时候,因为5的改变, [1,2,5,1,2,4,6] 的字典序就是 [1,2,4,6,5,2,1] 的下一个。
0 条评论